第13届广东工业大学ACM程序设计大赛 F-等式

发表于 | 浏览 次

题意

给定$n$，求${1\over x}+{1\over y}={1\over n} (x\le y) $的解数(x、y、n均为正整数)

题解

化简方程
$$
nx+ny=xy
$$
代入
$$
\\
\begin{cases}
x=n+a\\
y=n+b
\end{cases}
\\
$$
得
$$
n^2=ab
$$
即为求$n^2$的约数个数，约数个数定理可解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <vector>
#include "set"
using namespace std;
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
typedef long long ll;
const ll INF = 1e18;
const ll MAXN =1e5+100;
const ll MOD = 1e9+7;
const ll LIM= 1e5;
int prime[LIM+100],cnt;
bool isprime[LIM+100];
void linear()
{
    cnt=0;
    memset(isprime,1,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=LIM;i++)
    {
        if(isprime[i])prime[cnt++]=i;
         for(int j=0;j<cnt&&i*prime[j]<=LIM;j++)
         {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
    }
}

int main(int argc, char const *argv[]) {
    // FOP;
    linear();
    ll T_T;
    cin>>T_T;
    while(T_T--)
    {
        ll n;
        cin>>n;
        ll po[100];
        ll idx=0;
        Met(po,0);
        for(int i=0;i<cnt && prime[i]<=n;++i)
            if(!(n%prime[i]))
            {
                while (n%prime[i]==0) {
                    n/=prime[i];
                    po[idx]++;
                }
                idx++;
            }
        if(n>1)
        {
            po[idx]=1;
            idx++;
        }
        ll ans=1;
        for(int i=0;i<idx;++i)
            ans*=po[i]*2+1;
        cout<<(ans/2)+1<<endl;
    }
    return 0;
}