QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602180#9309. GraphlaurxhWA 7ms15860kbC++141.4kb2024-09-30 20:45:562024-09-30 20:46:08

Judging History

你现在查看的是最新测评结果

  • [2024-09-30 20:46:08]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:15860kb
  • [2024-09-30 20:45:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+7;
const int mod=998244353;
ll n,tot,cnt,len;
int vis[N],prime[N];
ll g[N],w[N],idx1[N],idx2[N];
void seive(){
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i;
        for(int j=1;j<=tot&&1ll*i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
ll kuasum(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
ll get_id(ll x){
    return (x<=len?idx1[x]:idx2[n/x]);
}
ll get(ll x){
    return g[get_id(x)];
}
signed main(){
    // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    seive();
    cin>>n;
    len=sqrt(n);
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);ll x=n/l;w[++cnt]=x;
        g[cnt]=x-1; 
        if(w[cnt]<=len)idx1[w[cnt]]=cnt;
        else idx2[n/w[cnt]]=cnt;     
    }
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=cnt&&1ll*prime[i]*prime[i]<=w[j];j++){
            int x=prime[i],r=w[j]/x;
            int k=get_id(r);
            g[j]-=g[k]-(i-1);
        }
    }
    ll ans=1;
    for(ll l=1,r;l<=n;l=r+1){
        ll x=n/l;
        r=n/x;
        if(x==1)continue;
        ll sum=get(x)-get(x/2);
        ll res=(sum%mod)*kuasum(x%mod,sum)%mod;
        ans=ans*kuasum(res,r-l+1);
    }  
    cout<<ans<<"\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 15860kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 15740kb

input:

2

output:

2

result:

wrong answer expected '1', found '2'