题目108：求解丢番图方程1/x + 1/y = 1/n
本帖最后由 欧拉计划 于 2016-8-21 00:41 编辑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 的一个简单版，强烈建议你先做这一个题目。
这题还是要找规律，通过观察前几个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 这个方程可以通过代换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的因数分解的个数。
好像并不对哦 永恒的蓝色梦想 发表于 2019-7-24 17:35
好像并不对哦
这个方程可以通过代换x=n+x1，y=n+y1。得到x1*y1=n^2。所以方程的解的个数等于n^2的因数分解中小于等于n的因数个数。 本帖最后由 代号-K 于 2020-4-9 20:12 编辑
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;
}
/*
答案：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;//p为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;
#pragma omp single
for (int i = 2; i <= M; ++i)
{
if (p < i)
continue;
for (int j = i * i; j < N; j += i)
p = 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;
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;
}
页:
[1]