Kuangbin【唯一分解定理】LCM数对

叁歲伎倆 2024-03-26 17:15 93阅读 0赞

**思路完全正确啊！！就差最后那个组合数了！！**

**感觉这个好坑**

[4586. LCM数对 - AcWing题库][4586. LCM_ - AcWing]

题意：

![c1cbf899d42e9045bf76782e4d37af96.png][]

思路：

暴力超时，肯定去考虑特殊性质

直接去考虑n的唯一分解

对于n的每一个质因子p：

其中有个数p的指数一定为a1，另一个的指数可以为0,1,2,.....a1

这样就是a1+1种情况

然后两个的位置可以换一下，因此要乘2

好了，止步于此，搞了很久样例都没过，呃呃

我忘记考虑了,i<=j的条件，因此答案还应该除2

又因为lcm(c,c)=c也算一种，因此答案还得+1

Code：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <map>
    //#define int long long
    using namespace std;
    using i64 = long long;
    const int mxn=1e7+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    vector<pair<int,int> > v;
    i64 n;
    int len=0,T=0;
    int vis[mxn],prime[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        int ans=1;
        v.clear();
        cin>>n;
        for(int i=1;i<=len&&prime[i]*prime[i]<=n;i++){
            int p=prime[i];
            if(n%p==0){
                int s=0;
                while(n%p==0){
                    n/=p;
                    s++;
                }
                ans*=(2*s+1);
            }
        }
        if(n>1) ans*=(2*1+1);
        cout<<"Case "<<++T<<": "<<ans/2+1<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        p_init(1e7);
        while(__--)solve();return 0;
    }

[4586. LCM_ - AcWing]: https://www.acwing.com/problem/content/description/4589/
[c1cbf899d42e9045bf76782e4d37af96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ef89d0b4e34c4a90a131ed170b42d01a.png