质数表的范围不是5e7？+不能预处理a%=mod？+94分#13求助

P1593 因子和

w_y_c @ 2021-02-17 13:01:48

三个问题求大佬帮看看

  1. 看题解知道了可以不用打表 但是抄了一份别人博客上打了表的数据范围不是5e7的也过了 就很疑惑 a如果是一个比较大的质数怎么办呢

  2. 用的是分治写的等比数列求和 于是我的所有运算过程都没有牵涉到除法 那么a%mod的这个预处理感觉就没毛病..

  3. 牛客和acwing过了 洛谷和poj没过...洛谷94分#13wa

    
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
typedef long long ll;
using namespace std;

const ll mod=9901; const int N=1e6+10; bool notPrime[N]; vector<int>prime; void init() { for (int i=2; i<sqrt(N); i++) { if (notPrime[i]) { continue; } for (int j=i; ji<N; j++) { notPrime[ij]=1; } } for (int i=2; i<N; i++) { if (!notPrime[i]) { prime.push_back(i); } } }

ll power(ll x,int n) { ll ret=1; x%=mod; while (n) { if (n&1) { ret=retx%mod; } x=xx%mod; n>>=1; } return ret; }

ll solve(int x,int b) { //x^0+....+x^b if (b==0) { return 1; } if (b&1) { return ((1+power(x, b/2+1))%modsolve(x, b/2)%mod); } else { return (((1+power(x, b/2))%modsolve(x, b/2-1)%mod)+power(x, b))%mod; } }

int main(int argc, const char argv[]) { int b,len; ll a,ans; vector<int>div;//质数除数 vector<int>divNum;//质数除数的个数 init(); len=prime.size(); while (cin>>a>>b) { div.clear(); divNum.clear(); for (int i=0; i<len; i++) { if (a<prime[i]) { break; } if (a%prime[i]==0) { div.push_back(prime[i]); ll tt=a; int cnt=0; while (tt%prime[i]==0) { tt/=prime[i]; cnt++; } divNum.push_back(cnt); } } ans=a>0; int num=div.size(); for (int i=0; i<num; i++) { ans=solve(div[i],b*divNum[i]); ans%=mod; } cout<<ans<<endl; } return 0; }

by w_y_c @ 2021-02-17 13:02:35

上面的代码糊了 重新来一份...

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
typedef long long ll;
using namespace std;

const ll mod=9901;
const int N=1e6+10;
bool notPrime[N];
vector<int>prime;
void init()
{
    for (int i=2; i<sqrt(N); i++) {
        if (notPrime[i]) {
            continue;
        }
        for (int j=i; j*i<N; j++) {
            notPrime[i*j]=1;
        }
    }
    for (int i=2; i<N; i++) {
        if (!notPrime[i]) {
            prime.push_back(i);
        }
    }
}

ll power(ll x,int n) {
    ll ret=1;
    x%=mod;
    while (n) {
        if (n&1) {
            ret=ret*x%mod;
        }
        x=x*x%mod;
        n>>=1;
    }
    return ret;
}

ll solve(int x,int b) {
    //x^0+....+x^b
    if (b==0) {
        return 1;
    }
    if (b&1) {
        return ((1+power(x, b/2+1))%mod*solve(x, b/2)%mod);
    } else {
        return (((1+power(x, b/2))%mod*solve(x, b/2-1)%mod)+power(x, b))%mod;
    }
}

int main(int argc, const char * argv[]) {
    int b,len;
    ll a,ans;
    vector<int>div;//质数除数
    vector<int>divNum;//质数除数的个数
    init();
    len=prime.size();
    while (cin>>a>>b) {
        div.clear();
        divNum.clear();
        for (int i=0; i<len; i++) {
            if (a<prime[i]) {
                break;
            }
            if (a%prime[i]==0) {
                div.push_back(prime[i]);
                ll tt=a;
                int cnt=0;
                while (tt%prime[i]==0) {
                    tt/=prime[i];
                    cnt++;
                }
                divNum.push_back(cnt);
            }
        }
        ans=a>0;
        int num=div.size();
        for (int i=0; i<num; i++) {
            ans*=solve(div[i],b*divNum[i]);
            ans%=mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

by w_y_c @ 2021-03-07 15:11:05

过了一段时间重新来看 自问自答 过不了的那个点就是这个帖子 https://www.luogu.com.cn/discuss/show/52497

里的大质数那一组数据

49999991 2

答案3423

不能预处理取模是因为我们是要对因数和取模 而不是对a^b取模 所以取模之后数据含义发生变化

by justforu @ 2023-11-07 09:02:24

感谢这组数据，卡在13了

|