第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--F-等式

链接：https://www.nowcoder.com/acm/contest/90/F
来源：牛客网

1.题目描述
给定n，求1/x + 1/y = 1/n （x<=y）的解数。（x、y、n均为正整数）
输入描述:
在第一行输入一个正整数T。
接下来有T行，每行输入一个正整数n，请求出符合该方程要求的解数。
（1<=n<=1e9）
输出描述:
输出符合该方程要求的解数。
示例1
输入
3
1
20180101
1000000000
输出
1
5
181
2.题目分析
3.代码如下

 1 #include<cstdio> 
 2 #include<cstring> 
 3 #include<algorithm> 
 4 #include<iostream> 
 5 #include<string> 
 6 #include<vector> 
 7 #include<stack> 
 8 #include<bitset>
 9 #include<cstdio> 
10 #include<cstdlib> 
11 #include<cmath> 
12 #include<set> 
13 #include<list> 
14 #include<deque> 
15 #include<map> 
16 #include<queue>
17 #include<algorithm> 
18 using namespace std; 
19 typedef long long ll; 
20 const double PI = acos(-1.0); 
21 const double eps = 1e-6; 
22 const int INF = 1000000000; 
23 const int maxn = 100; 
24 int gcd(int x,int y)
25 {       
26      if(y==0) return x;
27      return gcd(y,x%y);
28 }
29 int main()
30 {
31     int T;
32     scanf("%d",&T);//输入样例数目
33     while(T--)
34     {   
35         int n;
36         vector<int>vt;
37         scanf("%d",&n);
38         for(int i=1;i*i<=n;i++)
39             if(n%i==0) 
40             {   
41                 vt.push_back(i);
42                 if(i*i!=n) vt.push_back(n/i);
43             }
44         int l=vt.size();
45         int num=0;
46         for(int i=0;i<l;i++)
47             for(int j=0;j<=i;j++)
48                 if(gcd(vt[i],vt[j])==1) num++;     
49                     printf("%d
",num);    
50        }
51     return 0;
52 }

View Code