题目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

这题是参考了维基百科上的计算公式：
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[a]
                else:
                        break
                if b >= 0:
                        s += pdic[b]
                else:
                        break
                if c >= 0:
                        s -= pdic[c]
                else:
                        break
                if d >= 0:
                        s -= pdic[d]
                else:
                        break
        pdic[k] = s
        return s

for i in range(100000):
        if p(i) % 1000000 == 0:
                print (i)
                break

大约8秒钟可以出结果：
55374

guosl

这题也可以通过组合数学中的母函数展开来做。只是时间比较长。但可以用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[N];
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[i] = 0;
  for (int j = 0; j <= i; j += k)
  {
    p2[i] += p1[i - j];
    p2[i] %= 1000000;
  }
  if (i == k)
  {
    if (p2[k] == 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[i] = 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

from numba import jit

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

solve()

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

永恒的蓝色梦想

和76好像有点关系