欧拉计划 发表于 2015-11-5 17:17:04

题目78：考察硬币划分的方式数量

Coin partitions

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.
题目：

用 p(n) 表示 n 个硬币可以被划分成堆的方式。例如，5 个硬币可以被用 7 种方式划分成堆，所以 p(5)=7。

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

找到 p(n) 可以被一百万整除的最小的 n 。

jerryxjr1220 发表于 2016-12-31 20:37:01

这题是参考了维基百科上的计算公式：
According Wikipedia's information:
p(k) = p(k-(3*n*n-n)/2) + p(k-(3*n*n+n)/2) - p(k-(3*n*n+5*n+2)/2) - p(k-(3*n*n+7*n+4)/2) +... (n from 1 to ...) while p(0) = 1 and p(1) = 1
有了迭代公式，写程序相对还是比较容易的：
pdic = {0:1,1:1}
def p(k):
        global pdic
        s = 0
        if k == 0 or k == 1:
                return 1
        for n in range(1,int(k**0.5+1),2):
                a = k-(3*n*n-n)/2
                b = k-(3*n*n+n)/2
                c = k-(3*n*n+5*n+2)/2
                d = k-(3*n*n+7*n+4)/2
                if a >= 0:
                        s += pdic
                else:
                        break
                if b >= 0:
                        s += pdic
                else:
                        break
                if c >= 0:
                        s -= pdic
                else:
                        break
                if d >= 0:
                        s -= pdic
                else:
                        break
        pdic = s
        return s

for i in range(100000):
        if p(i) % 1000000 == 0:
                print (i)
                break
大约8秒钟可以出结果：
55374

guosl 发表于 2019-4-26 10:54:52

本帖最后由 guosl 于 2021-3-21 12:56 编辑

这题也可以通过组合数学中的母函数展开来做。只是时间比较长。但可以用GPU来编程计算。在GTX1060上2秒多点可以得出结果。
/*
用母函数展开来做
答案：55374
耗时：2.07287秒（GTX1060显卡）
*/
#include <iostream>
#include <algorithm>
#include <cuda_runtime.h>
#include <device_launch_parameters.h>
#include <helper_cuda.h>
using namespace std;

const int N = 64000;
const int nBlocksSize = 256;

int *a, *b, c;
bool *bFind;

__global__ void Polynomial_Mul(int *p1, int *p2, int k, bool *bFlag)
{
int i = blockIdx.x * nBlocksSize + threadIdx.x;
if (i >= N)
    return;
p2 = 0;
for (int j = 0; j <= i; j += k)
{
    p2 += p1;
    p2 %= 1000000;
}
if (i == k)
{
    if (p2 == 0)
      *bFlag = true;
}
}

void find_zero(int *p1, int *p2, int k)
{
Polynomial_Mul <<<N / nBlocksSize, nBlocksSize >>> (p1, p2, k, bFind);
}

int main(void)
{
cudaDeviceProp deviceProp;
int devID = gpuGetMaxGflopsDeviceId();
cudaSetDevice(devID);//设置计算卡
cudaGetDeviceProperties(&deviceProp, devID);
printf("GPU Device %d: \"%s\" with compute capability %d.%d\n\n",
    devID, deviceProp.name, deviceProp.major, deviceProp.minor);
//在显卡上分配内存
cudaMalloc((void**)&a, N * sizeof(int));
cudaMalloc((void**)&b, N * sizeof(int));
cudaMalloc((void**)&bFind, sizeof(int));
//设置计算的初始向量
for (int i = 0; i < N; ++i)
    c = 1;
cudaMemcpy(a, c, N * sizeof(int), cudaMemcpyHostToDevice);
int *p1 = a, *p2 = b;
for (int k = 2; k < N; ++k) //开始逐个展开母函数
{
    bool bFlag = false;//设置返回值的初值
    cudaMemcpy(bFind, &bFlag, sizeof(bool), cudaMemcpyHostToDevice);
    find_zero(p1, p2, k);//计算第k次展开
    swap(p1, p2);
    cudaGetLastError();
    cudaDeviceSynchronize();//等待计算完成
    cudaMemcpy(&bFlag, bFind, sizeof(bool), cudaMemcpyDeviceToHost);//获取本次计算的结果
    if (bFlag)//找到结果
    {
      cout << k << endl;
      break;
    }
}
cudaFree(a);
cudaFree(b);
cudaFree(bFind);
return 0;
}

fc1735 发表于 2020-6-4 14:52:29

from numba import jit

@jit
def solve():
mod = 10 ** 6
bound = 10 ** 5
dp = * bound
dp = 1
for i in range(1, bound):
    for j in range(i, bound):
      dp = (dp + dp) % mod
    if dp == 0:
      print(i)
      break

solve()

https://github.com/devinizz/project_euler/blob/master/page02/78.py

永恒的蓝色梦想 发表于 2021-1-11 12:46:37

和76好像有点关系
页: [1]
查看完整版本: 题目78：考察硬币划分的方式数量