QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602180 | #9309. Graph | laurxh | WA | 7ms | 15860kb | C++14 | 1.4kb | 2024-09-30 20:45:56 | 2024-09-30 20:46:08 |
Judging History
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'