给定$n$，求${1over x}+{1over y}={1over n} (xle 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 <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 ()
{
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[]) {
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;
}
|
近期评论