【约数】因子和

秒速五厘米 2024-03-30 12:19 101阅读 0赞

[P1593 因子和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1593 _ - _ _ _ _luogu.com.cn]

题意：

![ec305e5d4bd34ccdb41cab1bd0ffb18a.png][]

思路：

我们去枚举约数

如果直接枚举约数，超时

对于枚举约数，有两个trick：枚举倍数和唯一分解定理

我们考虑后者，对其分解质因数：

![34cc48b7cb8b43788c486e11eeba2688.png][]

因为它又有b的幂次：

![f49d5628aff64955a039f9ac08c2d8f9.png][]

因此答案就是：

![f358c6b781f64925b88a9c4962e5fa9c.png][]

这里可以直接用等比数列求和公式：

![c892b7f79fa748a793e249a64caa3500.png][]

因为是模意义下的答案，因此考虑逆元

但是mod=9901，容易出现逆元不存在的情况

逆元不存在时，有

![e098a01611f64b65b0272a1248ee7dd3.png][]

即

![6bcbfb1ed43e4ad2ac60ef6720624822.png][]

因此直接代入得

![2a4bfeb10867490c8418c48d10205265.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mod=9901;
    vector<pair<int,int> > v;
    int a,b,ans=1;
    int ksm(int a,int b,int mod){
        int res=1;
        while(b>0){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res%mod;
    }
    int calc(int p,int aa){
        if((1-p)%mod==0){
            return (1+aa)%mod;
        }
        int inv=ksm(1-p,mod-2,mod);
        return ((1-ksm(p,aa*b+1,mod))*inv)%mod;
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>a>>b;
        if(a==0){
            cout<<0<<'\n';
            return 0;
        }
        for(int i=2;i<=a/i;i++){
            if(a%i==0){
                int s=0;
                while(a%i==0) a/=i,s++;
                v.push_back({i,s});
            }
        }
        if(a>1) v.push_back({a,1});
        //for(int i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<'\n';
        int ans=1;
        for(int i=0;i<v.size();i++){
            ans*=calc(v[i].first,v[i].second);
            ans%=mod;
        }
        cout<<(ans%mod+mod)%mod<<'\n';
    }

**总结：**

**快速枚举约数：枚举倍数/唯一分解**

**数太大时考虑唯一分解**

**当模数比较小时要考虑逆元不存在的情况，不存在的话根据它的性质直接代入计算即可**

[P1593 _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1593
[ec305e5d4bd34ccdb41cab1bd0ffb18a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9615a03e9d8045c1bca26eddf8136c96.png
[34cc48b7cb8b43788c486e11eeba2688.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/54148ee5d11147b0afb78e556247db4f.png
[f49d5628aff64955a039f9ac08c2d8f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f0f0797a09594099aded2bd4e529c950.png
[f358c6b781f64925b88a9c4962e5fa9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5bd8b8530dac4fae9f5aa6d70208266e.png
[c892b7f79fa748a793e249a64caa3500.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ea8b2d8f29da4693905b235425dd3e49.png
[e098a01611f64b65b0272a1248ee7dd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c97b65855ca54998b9c683e8657ca1c2.png
[6bcbfb1ed43e4ad2ac60ef6720624822.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e164c6d43426422e9c12ff4cacdc71f3.png
[2a4bfeb10867490c8418c48d10205265.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/cb855333508343b28ee1857b3ed1241f.png