hdu 1299 Diophantus of Alexandria(数学题)

题目链接：hdu 1299 Diophantus of Alexandria

题意：

给你一个n，让你找1/x+1/y=1/n的方案数。

题解：

对于这种数学题，一般都变变形，找找规律，通过打表我们可以发现这个答案只与这个数的因子有关。

n=a₁^p₁*a₂^p₂*...*a_n^p_n

ans=((1+2*p₁)*(1+2*p₂)*...*(1+2*p_n)+1)/2

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=1e5+7;
 6 int primes[N],tot=0;
 7 bool vis[N];
 8 void Euler(){
 9     F(i,2,N-7){
10         if(!vis[i])primes[++tot]=i;
11         F(j,1,tot){
12             if(i*primes[j]>N)break;
13             vis[i*primes[j]]=1;
14             if(i%primes[j]==0)break;
15         }
16     }
17 }
18 
19 int t,n,ans,cas;
20 
21 int main()
22 {
23     Euler();
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d",&n);
28         ans=1;
29         F(i,1,tot)
30         {
31             if(primes[i]>n)break;
32             int cnt=0;
33             while(n%primes[i]==0)n/=primes[i],cnt++;
34             ans*=2*cnt+1;
35         }
36         if(n>1)ans*=3;
37         printf("Scenario #%d:
%d

",++cas,(ans+1)/2);
38     }
39     return 0;
40 }

View Code