Pairs Forming LCM LightOJ - 1236(唯一分解定理&&LCM)

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} p1k1​​p2k2​​p3k3​​p4k4​​...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} p1e1​​p2e2​​p3e3​​p4e4​​...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} p1f1​​p2f2​​p3f3​​p4f4​​...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​.

  1. 先看n的每个质因子,eg:p1
  2. 由于有 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的相对大小
  3. 那么就可以ans *= (2k+1).
  4. 最后考虑 i i i 和 j j j的大小,就是 ans/2.
  5. 最后,还要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;
}

上一篇:Codeforces 1178D. Prime Graph


下一篇:埃式筛