題意：
求 1/x+1/y=1/z x,y的整數(shù)解對(duì)數(shù)
做法：
先將y表示成 y=(x*z)/(x-z)
然后呢...我就不知道然后了
baidu了題解后才知道了
設(shè)w=x-z 則x=z+w 那么 y=(z*z+w*z)/w=z*z/w+z
所以轉(zhuǎn)化為了求z*z/w的整數(shù)解個(gè)數(shù)
即z*z的約數(shù)個(gè)數(shù) 因?yàn)橐笠粚?duì)的 所以答案是 (約數(shù)個(gè)數(shù)+1)/2
然后就解決了。
1 #include <cstdio>
2 #define n 50005
3 int p[n],T,N,ret;
4 bool mk[n];
5 inline void mkprime()
6 {
7 for (int i=2;i<n;++i)
8 if (!mk[i])
9 for (int j=i<<1;j<n;j+=i)
10 mk[j]=1;
11 for (int i=2;i<n;++i)
12 if (!mk[i]) p[++p[0]]=i;
13 }
14 inline int getlog(int &N,int prime)
15 {
16 int ret=0;
17 for (;N%prime==0;N/=prime,++ret);
18 return ret;
19 }
20 int main()
21 {
22 mkprime();
23 scanf("%d",&T);
24 for (int Te=1;Te<=T;++Te)
25 {
26 scanf("%d",&N);
27 ret=1;
28 for (int i=1;i<=p[0]&&p[i]*p[i]<=N;++i)
29 if (N%p[i]==0) ret*=(getlog(N,p[i])<<1)+1;
30 if (N>1) ret*=3;
31 printf("Scenario #%d:\n%d\n\n",Te,(ret+1)>>1);
32 }
33 return 0;
34 }
35