为什么我推的式子不行

P1593 因子和

yuyc @ 2023-11-10 08:48:04

\text{令} sum(p,c) = \sum_{i=0}^{c} (p^i) 即1+p^1+p^2+...+p^c \text{当}c为偶数时: sum(p,c) = 1 +...+p^{\frac{c}{2}}+p^{\frac{c}{2}+1}+...+p^c \hspace{1.54cm}=1+...+p^{\frac{c}{2}}+p^{\frac{c}{2}+1}(1 + ...+p^{\frac{c}{2} - 1}) \hspace{1.54cm}=(1+...+p^{\frac{c}{2}})+p^{\frac{c}{2}+1}(1 + ...+p^{\frac{c}{2} - 1}+p^{\frac{c}{2}}) -p^{c+1} \hspace{1.54cm}=(1 + p^{\frac{c}{2} + 1})\cdot sum(p,\frac{c}{2})-p^{c+1}
#include <bits/stdc++.h>
using namespace std;
int b;
const int mod = 9901;
struct node{
    int p = 0,c = 0;
    node (int _p,int _c) : p(_p),c(_c){};
};
vector<node> v;
int qmi(int a,int n){
    int res = 1;
    while(n){
        if(n & 1) res = res * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return res;
}
void cal(int a){
    for(int i=2;i<=sqrt(a);i++){
        if(a % i == 0){
//          node n = {a,0};
            v.push_back({i,0}); 
            while(a % i == 0){
                a /= i;
                v.back().c ++;
            }
            v.back().c *= b;
        }
    }
    if(a > 1){
        v.push_back({a,b});
    }
}
int sum(int p,int c){
    if(!c) return 1;
    if(c & 1){
        return ((1 + qmi(p,(c + 1) / 2)) % mod) * (sum(p,(c - 1) / 2) % mod);
    }else{
        return ((1 + qmi(p,(c / 2) + 1)) % mod) * (sum(p,c / 2) % mod) - qmi(p,c + 1);
        //return ((1 + qmi(p,c / 2) % mod) * ((sum(p,c / 2 - 1) % mod)) + qmi(p,c));改成这句就对了
    }
}
signed main(){
    int a,ans = 1;
    cin>>a>>b;
    if(a == 0){
        cout<<0;
        return 0;
    }
    cal(a);
/*  for(int i=0;i<v.size();i++){
        cout<<v[i].p<<' '<<v[i].c<<endl;
    }*/
    for(int i=0;i<v.size();i++){
//      cout<<v[i].p<<' '<<v[i].c<<endl;
        ans *= sum(v[i].p,v[i].c) % mod;
        ans %= mod;
    }
    cout<<ans;
    return 0;
}

by yuyc @ 2023-11-10 08:51:54

当p=13,c=190时,sum(p,c)结果为负数


by yukari1735 @ 2023-11-10 09:35:03

@yuyc 取模完的数做减法要加上模数,比如你在 \bmod p 下算 a-b,你需要写 (a-b+p)%p 这样。


by yukari1735 @ 2023-11-10 09:36:48

@yuyc 以及你的代码似乎在哪里会爆 int,我全改成 long long 再加上前面的那个就通过了。


by yuyc @ 2023-11-10 09:59:45

@yukari1735 学到了,谢谢你


|