xtu oj 不定方程的正整数解

回顾

• A+B III
• 问题 H: 三角数
• 问题 G: 3个数
• 等式 数组下标查询，降低时间复杂度
• 1405 问题 E: 世界杯
• xtu 数码串
• xtu oj 神经网络
• xtu oj 1167 逆序数（大数据）
• xtu oj 原根

思路

首先直观地理解这个题目的意思，用 a=6 这个样例去思考，我凑了一下，发现直观地算找出这四个答案组数不是那么好找。分别是 x=2,y=3 ，x=3,y=6 ，x=4,y=12 ，x=5,y=30 ，我就在想计算机需要循环去思考，从小到大去循环，那么我们再观察给的表达式，x 一定要小于 a ，这样才能使得 x 的倒数比 a 的倒数大，才能找到正整数解，同理 y 一定要比 x 大，分子相同分母越大，分数越小。

所以我们可以发现 x 的取值是有一个范围的，从 1 到 a-1 ，不能取到 a ，假设取到 a ，此时减去 0 才是 1/a ，但是 1/y 显然不能取 0 ，以这个作为出发点，把 x 和 a 都当作参数，算出 y 的表达式，y=(a*x)/(a-x) ，需要满足的条件是正整数，并且 y>x

需要注意的代码细节是需要使用 long long ，我其实最开始注意了，可能漏了一些变量，直接 WA 了，后面把 a 和 x 也改成 long long 才过掉这题。

c 语言代码

#include<stdio.h>
#define LL long long int main(){int t;scanf("%d",&t);while(t--){LL a;scanf("%lld",&a);int ans=0;for(LL x=1;x<=a-1;x++){LL up=a*x;LL down=a-x;if(up%down==0){LL temp=up/down;if(temp>x){ans++;}}}printf("%d\n",ans);}return 0;
}