第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.题目分析 n=(x∗y)/(x y)n=(x∗y)/(x y)n = (x*y)/(x y) (x y)∗n=x∗y(x y)∗n=x∗y(x y)*n= x*y 设x=n a,y=n bx=n a,y=n bx = n a,y = n b 带入可以得到 n2=a∗bn2=a∗bn^2= a*b 题目就转化成了求所有整数对使得a∗b=n∗na∗b=n∗na*b = n*n。即求n2n2n^2的约数个数，由于约数都是成对出现的，两数乘积为n2n2n^2，为奇数是因为nnn与nnn成对出现，而只计算了1次。为避免重复，设约数个数为ppp，(p 1)/2(p 1)/2(p 1)/2即为所求。然而n2n2n^2过大不能直接求约数。我们用求质因子的方法求约数个数，只需求nnn的素因子，每个个数乘2即为n2n2n^2的每个素因子个数。
3.代码如下

代码语言：javascript复制

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#include<iostream> 
#include<string> 
#include<vector> 
#include<stack> 
#include<bitset>
#include<cstdio> 
#include<cstdlib> 
#include<cmath> 
#include<set> 
#include<list> 
#include<deque> 
#include<map> 
#include<queue>
#include<algorithm> 
using namespace std; 
typedef long long ll; 
const double PI = acos(-1.0); 
const double eps = 1e-6; 
const int INF = 1000000000; 
const int maxn = 100; 
int gcd(int x,int y)
{       
     if(y==0) return x;
     return gcd(y,x%y);
}
int main()
{
    int T;
    scanf("%d",&T);//输入样例数目
    while(T--)
    {   
        int n;
        vector<int>vt;
        scanf("%d",&n);
        for(int i=1;i*i<=n;i  )
            if(n%i==0) 
            {   
                vt.push_back(i);
                if(i*i!=n) vt.push_back(n/i);
            }
        int l=vt.size();
        int num=0;
        for(int i=0;i<l;i  )
            for(int j=0;j<=i;j  )
                if(gcd(vt[i],vt[j])==1) num  ;     
                    printf("%dn",num);    
       }
    return 0;
}

0 人点赞