QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #412149 | #3161. Another Coin Weighing Puzzle | littlecat# | AC ✓ | 56ms | 8500kb | C++14 | 843b | 2024-05-16 09:17:19 | 2024-05-16 09:17:20 |
Judging History
answer
#include <iostream>
using namespace std;
typedef long long ll;
const int mx=1000000; const ll mod=998244353;
ll pow(ll x, int e)
{
if(!e) return 1; ll t=pow(x,e>>1); t=(t*t)%mod;
if(e&1) t=(t*x)%mod; return t;
}
int u[mx+1]; bool p[mx+1];
int main()
{
//count no. gcd 1 n-tuples of -k..k
//t|gcd: (2(k/t)+1)^n; PIE: mobius inversion
int n; ll k, ans=1; cin>>n>>k;
for(int i=2; i<=mx; i++) p[i]=1;
for(int i=2; i<=1000; i++) if(p[i]) for(int j=i+i; j<=mx; j+=i) p[j]=0;
for(int i=2; i<=mx; i++) if(p[i])
{
for(int j=i; j<=mx; j+=i) u[j]++;
if(i<=1000) for(int j=i*i; j<=mx; j+=i*i) u[j]=-mx;
}
for(int i=1; i<=mx; i++) u[i]=(u[i]<0)?0:((u[i]&1)?-1:1);
for(int i=1; i<=k; i++) if(u[i]) ans+=(pow(2*(k/i)+1,n)-1)*u[i];
cout<<((ans%mod)+mod)%mod<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 10ms
memory: 8312kb
input:
2 1
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 10ms
memory: 8376kb
input:
2 2
output:
17
result:
ok single line: '17'
Test #3:
score: 0
Accepted
time: 5ms
memory: 8428kb
input:
10000 10000
output:
689223145
result:
ok single line: '689223145'
Test #4:
score: 0
Accepted
time: 4ms
memory: 8500kb
input:
9999 31
output:
986106162
result:
ok single line: '986106162'
Test #5:
score: 0
Accepted
time: 10ms
memory: 8280kb
input:
57 9817
output:
447253096
result:
ok single line: '447253096'
Test #6:
score: 0
Accepted
time: 9ms
memory: 8492kb
input:
501 499
output:
247755220
result:
ok single line: '247755220'
Test #7:
score: 0
Accepted
time: 17ms
memory: 8376kb
input:
97424 174829
output:
964884269
result:
ok single line: '964884269'
Test #8:
score: 0
Accepted
time: 6ms
memory: 8376kb
input:
11 13
output:
729153057
result:
ok single line: '729153057'
Test #9:
score: 0
Accepted
time: 13ms
memory: 8308kb
input:
200000 200000
output:
803771125
result:
ok single line: '803771125'
Test #10:
score: 0
Accepted
time: 10ms
memory: 8280kb
input:
199999 562
output:
865836540
result:
ok single line: '865836540'
Test #11:
score: 0
Accepted
time: 15ms
memory: 8368kb
input:
3539 189423
output:
530738158
result:
ok single line: '530738158'
Test #12:
score: 0
Accepted
time: 13ms
memory: 8372kb
input:
198324 173852
output:
963717515
result:
ok single line: '963717515'
Test #13:
score: 0
Accepted
time: 4ms
memory: 8424kb
input:
1 1
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 56ms
memory: 8308kb
input:
1000000 1000000
output:
800590912
result:
ok single line: '800590912'
Test #15:
score: 0
Accepted
time: 36ms
memory: 8412kb
input:
5034 999999
output:
946555033
result:
ok single line: '946555033'
Test #16:
score: 0
Accepted
time: 7ms
memory: 8372kb
input:
999998 2042
output:
713878368
result:
ok single line: '713878368'