Pairs Forming LCM LightOJ - 1236
题意：
给你一个n。问有多少对pair（i，j）。（i <= j）
思路：
可以想到
n =
p
1
k
1
p
2
k
2
p
3
k
3
p
4
k
4
.
.
.
p
m
k
m
p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...p_m^{k_m}
p1k1p2k2p3k3p4k4...pmkm
i =
p
1
e
1
p
2
e
2
p
3
e
3
p
4
e
4
.
.
.
p
m
e
m
p_1^{e_1}p_2^{e_2}p_3^{e_3}p_4^{e_4}...p_m^{e_m}
p1e1p2e2p3e3p4e4...pmem
j =
p
1
f
1
p
2
f
2
p
3
f
3
p
4
f
4
.
.
.
p
m
f
m
p_1^{f_1}p_2^{f_2}p_3^{f_3}p_4^{f_4}...p_m^{f_m}
p1f1p2f2p3f3p4f4...pmfm
那么 lcm(i，j) =
p
1
m
a
x
（
e
1
，
f
1
）
p
2
m
a
x
（
e
2
，
f
2
）
p
3
m
a
x
（
e
3
，
f
3
）
.
.
.
p
m
m
a
x
（
e
m
，
f
m
）
p_1^{max（e_1，f_1）}p_2^{max（e_2，f_2）}p_3^{max（e_3，f_3）}...p_m^{max（e_m，f_m）}
p1max（e1，f1）p2max（e2，f2）p3max（e3，f3）...pmmax（em，fm）
要满足lcm（i，j） = n。
那么max（
e
1
e_1
e1，
f
1
f_1
f1）= k1.
max（
e
2
e_2
e2，
f
2
f_2
f2）= k2.
max（
e
3
e_3
e3，
f
3
f_3
f3）= k3.
…
max（
e
m
e_m
em，
f
m
f_m
fm）=
k
m
k_m
km.
- 先看n的每个质因子，eg：p1
- 由于有
i
i
i 和
j
j
j，所以固定
i
i
i 时（
i
i
i的p1这个质因子取k1个），
j
j
j有k1+1种选择。相反固定
j
j
j时，
i
i
i也有k1+1种选择。但是两者都有k1，所以要减一。（
这里先不考虑i和j的相对大小） - 那么就可以ans *= （2k+1）.
- 最后考虑 i i i 和 j j j的大小，就是 ans/2.
- 最后，还要ans++。因为 i = j = n i=j=n i=j=n这种情况被忽略了。
AC
#include <iostream>
#include <vector>
#include <algorithm>
#define sz(a) (int)a.size()
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
const int N = 1e6+10;
bool vis[maxn];
vector<ll>prime, pri, pri_num;
int cnt = 0;
void table(){
vis[1] = 1;
fori(i,2,maxn){
if(!vis[i]){
prime.pb(i); cnt++;
for(int j = i*2; j < maxn; j += i)vis[j] = 1;
}
}
}
void divide(ll x){
pri.clear(); pri_num.clear();
for(int i = 0; i < cnt && prime[i]*prime[i] <= x; i++){
int tem = prime[i];
if(x % tem == 0){
pri.pb(tem);
int tot = 0;
while(x % tem == 0){
x /= tem;
tot++;
}
pri_num.pb(tot);
}
}
if(x>1){ pri.pb(x); pri_num.pb(1);}
return ;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tt, kase = 0; cin>>tt;
table();
while(tt--){
ll n; cin>>n;
ll ans = 1;
divide(n);
fori(i, 0, sz(pri)){
ll tmp = pri_num[i] * 2 + 1;
ans *= tmp;
}
ans = ans/2 +1;
cout<<"Case "<<++kase<<": "<<ans<<endl;
}
return 0;
}