QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #604839 | #8761. 另一个计数问题 | Kanate# | AC ✓ | 1772ms | 113456kb | C++14 | 7.1kb | 2024-10-02 14:11:58 | 2024-10-02 14:11:59 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
template<class T>void chkmax(T &a,T b){a=max(a,b);}
template<class T>void chkmin(T &a,T b){a=min(a,b);}
template<class T>T read(T &x)
{
x=0;T f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
return x*=f;
}
template<class T,class ...L>void read(T &x,L &...l){read(x),read(l...);}
template<class T>void write(T x)
{
if(x<0){putchar('-');x=-x;}
if(x>9){write(x/10);}putchar(x%10+'0');
}
template<class T>void write(T x,char c){write(x),putchar(c);}
int qpow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
b>>=1;a=a*a%mod;
}
return ans;
}
int inv(int x){return qpow(x,mod-2);}
int N,n;
int A,B,C,D,E,F,G;
int isprime(int x)
{
for(int i=2;i*i<=x;i++)
if(x%i==0)
return 0;
return 1;
}
int fa[10005];
int find(int n){return fa[n]==n?n:fa[n]=find(fa[n]);}
void bruteforce(int N)
{
rep(i,2,N)fa[i]=i;
rep(i,2,N)for(int j=2*i;j<=N;j+=i)
fa[find(i)]=fa[find(j)];
int ans=0;
rep(i,2,N-1)rep(j,i+1,N)if(find(i)==find(j))
ans=(i*j%mod+ans)%mod;
write(ans,'\n');
}
#define LL long long
#define V 1000005
const int pw6=inv(6);
const int pw2=inv(2);
namespace Min254 {
int prime[V], id1[V], id2[V], flag[V], ncnt, m;
LL g[V], sum[V], a[V], T, n;
inline int ID(LL x) {
return x <= T ? id1[x] : id2[n / x];
}
inline LL calc(LL x) {
x%=mod;
return (x * (x + 1) %mod * (2*x+1)%mod *pw6%mod - 1 +mod)%mod;
}
inline LL f(LL x) {
return x * x %mod;
}
inline void init() {
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = (sum[ncnt - 1] + i * i %mod )%mod;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++) {
g[j] = g[j] - (LL)prime[i]*prime[i]%mod* ((g[ID(a[j] / prime[i])] - sum[i - 1]+mod)%mod) %mod;
g[j] = (g[j] %mod + mod) %mod;
}
}
inline LL solve(LL x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}
}
namespace Min252 {
int prime[V], id1[V], id2[V], flag[V], ncnt, m;
LL g[V], sum[V], a[V], T, n;
inline int ID(LL x) {
return x <= T ? id1[x] : id2[n / x];
}
inline LL calc(LL x) {
x%=mod;
return (x * (x + 1) %mod * (2*x+1)%mod *pw6%mod - 1 +mod)%mod;
}
inline LL f(LL x) {
return x * x %mod;
}
inline void init() {
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = (sum[ncnt - 1] + i * i %mod )%mod;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++) {
g[j] = g[j] - (LL)prime[i]*prime[i]%mod* ((g[ID(a[j] / prime[i])] - sum[i - 1]+mod)%mod) %mod;
g[j] = (g[j] %mod + mod) %mod;
}
}
inline LL solve(LL x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}
}
namespace Min251 {
int prime[V], id1[V], id2[V], flag[V], ncnt, m;
LL g[V], sum[V], a[V], T, n;
inline int ID(LL x) {
return x <= T ? id1[x] : id2[n / x];
}
inline LL calc(LL x) {
x%=mod;
return (x * (x + 1)%mod * pw2 %mod - 1 +mod)%mod;
}
inline LL f(LL x) {
return x;
}
inline void init() {
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = (sum[ncnt - 1] + i ) %mod;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++) {
g[j] = g[j] - (LL)prime[i] * ((g[ID(a[j] / prime[i])] - sum[i - 1] + mod)%mod) %mod;
g[j] = (g[j] %mod + mod) %mod;
}
}
inline LL solve(LL x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}
}
namespace Min253 {
int prime[V], id1[V], id2[V], flag[V], ncnt, m;
LL g[V], sum[V], a[V], T, n;
inline int ID(LL x) {
return x <= T ? id1[x] : id2[n / x];
}
inline LL calc(LL x) {
x%=mod;
return (x * (x + 1)%mod * pw2 %mod - 1 +mod)%mod;
}
inline LL f(LL x) {
return x;
}
inline void init() {
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = (sum[ncnt - 1] + i ) %mod;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++) {
g[j] = g[j] - (LL)prime[i] * ((g[ID(a[j] / prime[i])] - sum[i - 1] + mod)%mod) %mod;
g[j] = (g[j] %mod + mod) %mod;
}
}
inline LL solve(LL x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}
}
signed main()
{
read(N);
// rep(i,1,200)
// write(i,' '),bruteforce(i);
n=N%mod;
C=(n*(n+1)%mod*inv(2)%mod+mod-1)%mod;
D=(n*(n+1)%mod*((2*n+1)%mod)%mod*inv(6)%mod+mod-1)%mod;
B=C*C%mod;
// write(C,' ');write(D,' ');
// rep(i,(N+1)/2,N)if(isprime(i))
// E=(E+i)%mod,F=(i*i%mod+F)%mod;
E=((Min251::solve(N)-Min253::solve(N/2))%mod+mod)%mod;
F=((Min252::solve(N)-Min254::solve(N/2))%mod+mod)%mod;
// write(E,' ');write(F,' ');
int ans=((B+E*E%mod-(2*C*E%mod)+F-D)%mod+mod)%mod*inv(2)%mod;
write(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38516kb
input:
4
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 38512kb
input:
5
output:
8
result:
ok 1 number(s): "8"
Test #3:
score: 0
Accepted
time: 0ms
memory: 38364kb
input:
6
output:
80
result:
ok 1 number(s): "80"
Test #4:
score: 0
Accepted
time: 0ms
memory: 38416kb
input:
7
output:
80
result:
ok 1 number(s): "80"
Test #5:
score: 0
Accepted
time: 0ms
memory: 42616kb
input:
8
output:
200
result:
ok 1 number(s): "200"
Test #6:
score: 0
Accepted
time: 0ms
memory: 42592kb
input:
9
output:
407
result:
ok 1 number(s): "407"
Test #7:
score: 0
Accepted
time: 0ms
memory: 42436kb
input:
10
output:
937
result:
ok 1 number(s): "937"
Test #8:
score: 0
Accepted
time: 0ms
memory: 42580kb
input:
79
output:
3224298
result:
ok 1 number(s): "3224298"
Test #9:
score: 0
Accepted
time: 0ms
memory: 42612kb
input:
123
output:
21077222
result:
ok 1 number(s): "21077222"
Test #10:
score: 0
Accepted
time: 0ms
memory: 42592kb
input:
158
output:
57411585
result:
ok 1 number(s): "57411585"
Test #11:
score: 0
Accepted
time: 0ms
memory: 42616kb
input:
285
output:
605750829
result:
ok 1 number(s): "605750829"
Test #12:
score: 0
Accepted
time: 0ms
memory: 42592kb
input:
355
output:
509863120
result:
ok 1 number(s): "509863120"
Test #13:
score: 0
Accepted
time: 0ms
memory: 42524kb
input:
484
output:
311440260
result:
ok 1 number(s): "311440260"
Test #14:
score: 0
Accepted
time: 0ms
memory: 42464kb
input:
520
output:
102191845
result:
ok 1 number(s): "102191845"
Test #15:
score: 0
Accepted
time: 0ms
memory: 42552kb
input:
706
output:
300787918
result:
ok 1 number(s): "300787918"
Test #16:
score: 0
Accepted
time: 0ms
memory: 42676kb
input:
747
output:
505062591
result:
ok 1 number(s): "505062591"
Test #17:
score: 0
Accepted
time: 0ms
memory: 42596kb
input:
784
output:
181810798
result:
ok 1 number(s): "181810798"
Test #18:
score: 0
Accepted
time: 0ms
memory: 42712kb
input:
76879
output:
716166793
result:
ok 1 number(s): "716166793"
Test #19:
score: 0
Accepted
time: 0ms
memory: 42572kb
input:
209295
output:
753032272
result:
ok 1 number(s): "753032272"
Test #20:
score: 0
Accepted
time: 0ms
memory: 42484kb
input:
220895
output:
874612082
result:
ok 1 number(s): "874612082"
Test #21:
score: 0
Accepted
time: 0ms
memory: 44592kb
input:
243390
output:
68635874
result:
ok 1 number(s): "68635874"
Test #22:
score: 0
Accepted
time: 3ms
memory: 42584kb
input:
414767
output:
862578797
result:
ok 1 number(s): "862578797"
Test #23:
score: 0
Accepted
time: 0ms
memory: 42636kb
input:
431662
output:
231728766
result:
ok 1 number(s): "231728766"
Test #24:
score: 0
Accepted
time: 0ms
memory: 42640kb
input:
521130
output:
106207351
result:
ok 1 number(s): "106207351"
Test #25:
score: 0
Accepted
time: 0ms
memory: 42496kb
input:
668419
output:
580625063
result:
ok 1 number(s): "580625063"
Test #26:
score: 0
Accepted
time: 0ms
memory: 42544kb
input:
700378
output:
790849562
result:
ok 1 number(s): "790849562"
Test #27:
score: 0
Accepted
time: 3ms
memory: 42652kb
input:
965876
output:
856082142
result:
ok 1 number(s): "856082142"
Test #28:
score: 0
Accepted
time: 68ms
memory: 51952kb
input:
998244350
output:
539142456
result:
ok 1 number(s): "539142456"
Test #29:
score: 0
Accepted
time: 72ms
memory: 47920kb
input:
998244351
output:
730264865
result:
ok 1 number(s): "730264865"
Test #30:
score: 0
Accepted
time: 68ms
memory: 47972kb
input:
998244352
output:
326703895
result:
ok 1 number(s): "326703895"
Test #31:
score: 0
Accepted
time: 63ms
memory: 49964kb
input:
998244353
output:
326703895
result:
ok 1 number(s): "326703895"
Test #32:
score: 0
Accepted
time: 63ms
memory: 45856kb
input:
998244354
output:
730264864
result:
ok 1 number(s): "730264864"
Test #33:
score: 0
Accepted
time: 72ms
memory: 47896kb
input:
998244355
output:
539142451
result:
ok 1 number(s): "539142451"
Test #34:
score: 0
Accepted
time: 68ms
memory: 49936kb
input:
998244356
output:
751581014
result:
ok 1 number(s): "751581014"
Test #35:
score: 0
Accepted
time: 118ms
memory: 52296kb
input:
2165916141
output:
216013547
result:
ok 1 number(s): "216013547"
Test #36:
score: 0
Accepted
time: 173ms
memory: 60976kb
input:
3550627266
output:
318019384
result:
ok 1 number(s): "318019384"
Test #37:
score: 0
Accepted
time: 389ms
memory: 68856kb
input:
11640239920
output:
137498099
result:
ok 1 number(s): "137498099"
Test #38:
score: 0
Accepted
time: 486ms
memory: 68408kb
input:
16191777349
output:
991399721
result:
ok 1 number(s): "991399721"
Test #39:
score: 0
Accepted
time: 774ms
memory: 84212kb
input:
31326230483
output:
99981147
result:
ok 1 number(s): "99981147"
Test #40:
score: 0
Accepted
time: 799ms
memory: 78480kb
input:
32810385543
output:
284259680
result:
ok 1 number(s): "284259680"
Test #41:
score: 0
Accepted
time: 877ms
memory: 86360kb
input:
37368395332
output:
511468046
result:
ok 1 number(s): "511468046"
Test #42:
score: 0
Accepted
time: 930ms
memory: 83924kb
input:
40002331093
output:
282851705
result:
ok 1 number(s): "282851705"
Test #43:
score: 0
Accepted
time: 1548ms
memory: 102392kb
input:
82884464396
output:
767050832
result:
ok 1 number(s): "767050832"
Test #44:
score: 0
Accepted
time: 1718ms
memory: 102680kb
input:
96506992785
output:
31413975
result:
ok 1 number(s): "31413975"
Test #45:
score: 0
Accepted
time: 1768ms
memory: 111556kb
input:
99999999995
output:
456189842
result:
ok 1 number(s): "456189842"
Test #46:
score: 0
Accepted
time: 1758ms
memory: 107212kb
input:
99999999996
output:
516138273
result:
ok 1 number(s): "516138273"
Test #47:
score: 0
Accepted
time: 1756ms
memory: 110928kb
input:
99999999997
output:
136420410
result:
ok 1 number(s): "136420410"
Test #48:
score: 0
Accepted
time: 1760ms
memory: 106364kb
input:
99999999998
output:
841974696
result:
ok 1 number(s): "841974696"
Test #49:
score: 0
Accepted
time: 1759ms
memory: 113456kb
input:
99999999999
output:
164762165
result:
ok 1 number(s): "164762165"
Test #50:
score: 0
Accepted
time: 1772ms
memory: 110376kb
input:
100000000000
output:
627965619
result:
ok 1 number(s): "627965619"