「题解」整除 division(未完待续)

题目链接:GMOJ 6272

题目

题目描述

输入格式

输出格式

数据范围

时空限制

题解

本题有多种解法,详情请看下一页。

解法 A (暴力解法)

未完待续

思路

代码

#include<cstdio>
typedef long long ll;
#define MOD 998244353ll
const int MAXC=50+5;
const int MAXt=10000;
const int MAXM=1000000000;
const int MAXT=10000;
int T,m;
int C,c[MAXC];
ll pow(ll,ll,ll);
int main(void){
    //freopen("division.in","r",stdin);
    //freopen("division.out","w",stdout);
    register int i,x;
    register ll ans,sum;
    scanf("%*d");
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&C,&m);
        for(i=1;i<=C;++i)
            scanf("%d",&c[i]);
        ans=1;
        for(i=1;i<=C;++i){
            sum=0;
            for(x=1;x<=c[i];++x)
                if(x%c[i]==0||pow(x,m-1,c[i])==1)
                    ++sum;
            ans=(ans*sum)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
ll pow(ll x,ll exp,ll mod){
    if(!exp)
        return 1;
    else if(exp==1)
        return x;
    else if(exp&1){
        ll temp=pow(x,exp>>1,mod);
        return (temp*temp%mod)*x%mod;
    }
    else{
        ll temp=pow(x,exp>>1,mod);
        return temp*temp%mod;
    }
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
typedef long long ll;
#define MOD 998244353ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXC=50+5;
const int MAXt=10000+5;
const int MAXM=1000000000;
const int MAXT=10000;
bool flag[MAXt];
int T,m;
int C,c[MAXC];
int cnt,Power[MAXt],prime[MAXt];
inline int func(int);
inline int pow(int,int,int);
int main(void){
    //freopen("division.in","r",stdin);
    //freopen("division.out","w",stdout);
    register int i;
    register ll ans;
    read();
    T=read();
    while(T--){
        C=read(),m=read();
        ans=1;
        for(i=1;i<=C;++i){
            c[i]=read();
            ans=ans*func(c[i])%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
inline int func(int c){
    register int i,j,res=1;
    memset(flag,0,sizeof(flag));
    cnt=0;
    Power[1]=1;
    for(i=2;i<c;++i){
        if(!flag[i]){
            prime[++cnt]=i;
            Power[i]=pow(i,m,c);
        }
        for(j=1;j<=cnt;++j){
            if(prime[j]*i>c)
                break;
            flag[prime[j]*i]=true;
            Power[prime[j]*i]=Power[prime[j]]*Power[i]%c;
            if(i%prime[j]==0)
                break;
        }
    }
    for(i=1;i<c;++i)
        res+=(Power[i]==i);
    return res;
}
inline int pow(int x,int exp,int mod){
    register int res=1;
    while(exp){
        if(exp&1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        exp>>=1;
    }
    return res;
}