题目108：求解丢番图方程1/x + 1/y = 1/n

欧拉计划

Diophantine reciprocals I

In the following equation x, y, and n are positive integers.

For n = 4 there are exactly three distinct solutions:

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

NOTE: This problem is an easier version of Problem 110; it is strongly advised that you solve this one first.

题目：

在如下方程中，x，y 和 n 皆为正整数。

对于 n=4，一共有三个不同的解：

要使方程拥有超过一千个不同的解，最小的 n 是多少？

注意：该题目是题目 110 的一个简单版，强烈建议你先做这一个题目。

jerryxjr1220

这题还是要找规律，通过观察前几个n（n>60），可以发现，基本上每个不同解的个数+1，n都是60的倍数。

n = 60
while True:
        count = 0
        for x in range(n+1,2*n+1):
                if x*n % (x-n) == 0:
                        count += 1
        if count > 1000:
                break
        n += 60
print (n, count)

答案180180

guosl

这个方程可以通过代换x=n+x1，y=n+y1。得到x1*y1=n^2。所以方程的解的个数等于n^2的因数分解的个数。

永恒的蓝色梦想

guosl 发表于 2019-4-26 10:50
这个方程可以通过代换x=n+x1，y=n+y1。得到x1*y1=n^2。所以方程的解的个数等于n^2的因数分解的个数。

好像并不对哦

guosl

永恒的蓝色梦想 发表于 2019-7-24 17:35
好像并不对哦

这个方程可以通过代换x=n+x1，y=n+y1。得到x1*y1=n^2。所以方程的解的个数等于n^2的因数分解中小于等于n的因数个数。

代号-K

110 的 answer is ： 1260
由于 n 的 可拆解 为  n^2 中 两个因数的乘积
所以可以编写代码如下：

void getDiophantineReciprocals(int flag){
    int num = 1;
    int count;
    int i;
    ElementType numPow;
    while(true){
        count = 1;
        i = 2;
        num++;
        numPow = (ElementType) pow(num, 2);
        while(i <= num){
            if(numPow % i == 0){
                count++;
            }
            i++;
        }
        if(count >= flag){
            printf("get it\n");
            printf("%d has %d\n", num,count);
            return;
        }
        printf("%d has %d\n",num,count);
    }
}

int main(int argc, char *argv[]){
    getDiophantineReciprocals(110);
    return 0;
}

guosl

/*
答案：180180
耗时：0.0027585秒
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;

const int N = 1000000;
const int M = 1000;
const int nSteps = 100;
int p[N];//p[i]为i的一个素因数，用于i的素因数分解

int main(void)
{
  int nK = 5;
  volatile bool bContinue = true;
  int nMinK = 0x7fffffff;
  double t = omp_get_wtime();
#pragma omp parallel shared(nK,bContinue) reduction(min:nMinK)
  {
    //应用筛法求每个数的一个素因数
#pragma omp for
    for (int i = 1; i < N; ++i)
      p[i] = i;
#pragma omp single
    for (int i = 2; i <= M; ++i)
    {
      if (p[i] < i)
        continue;
      for (int j = i * i; j < N; j += i)
        p[j] = i;
    }
    while (bContinue)
    {
      int k = 0;
#pragma omp critical(c1)
      {
        k = nK;
        nK += nSteps;
      }
      for (int i = k; i < k + nSteps; ++i)
      {
        //对i^2求其因数的分解
        int nCount = 1;//记录i的因数个数
        int x = i;
        while (x > 1)
        {
          int y = 0, z = p[x];
          while ((x % z) == 0)
          {
            ++y;
            x /= z;
          }
          nCount *= (2 * y + 1);
        }
        if (nCount > 2000)//此时至少有1000个因数小于i
        {
          nMinK = min(nMinK, i);
#pragma omp critical(c2)
          bContinue = false;
          break;
        }
      }
    }
  }
  t = omp_get_wtime() - t;
  cout << nMinK << endl << t << endl;
  return 0;
}