QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#451266	#8761. 另一个计数问题	tarjen	AC ✓	1399ms	113156kb	C++20	4.1kb	2024-06-23 01:48:24	2024-06-23 01:48:24

Judging History

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

[2024-06-23 01:48:24]
评测

测评结果：AC
用时：1399ms
内存：113156kb

查看

[2024-06-23 01:48:24]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod=998244353;
const int Ny2=(mod+1)/2; 
const int Ny6=166374059;
const int N=1e6+10;
namespace Min25_1{

    int prime[N], id1[N], id2[N], flag[N], ncnt, m;

    int g[N], sum[N], a[N], T, n;
    inline void fff()
    {
        for(int i=0;i<N;i++){
            prime[i]=0;
            id1[i]=0;
            id2[i]=0;
            flag[i]=0;
            g[i]=0;
            sum[i]=0;
            a[i]=0;
        }
        ncnt=0;
        m=0;
        T=0;
        n=0;
    }
    inline int ID(int x) {
        return x <= T ? id1[x] : id2[n / x];
    }

    inline int calc(int x) {
        x%=mod;
        return (x * (x + 1)%mod*Ny2%mod - 1+mod)%mod;
    }

    inline int f(int x) {
        return x;
    }

    inline void init() {
        T = sqrtl(n + 0.5)+100;
        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 (int 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 && (int)prime[i] * prime[i] <= a[j]; j++)
                g[j] = g[j] - prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]+mod)%mod,
                g[j]=(g[j]%mod+mod)%mod;
    }

    inline int solve(int x) {
        fff();
        if (x <= 1) return x;
        return n = x, init(), g[ID(n)];
    }

}
namespace Min25_2 {

    int prime[N], id1[N], id2[N], flag[N], ncnt, m;

    int g[N], sum[N], a[N], T, n;
    inline void fff()
    {
        for(int i=0;i<N;i++){
            prime[i]=0;
            id1[i]=0;
            id2[i]=0;
            flag[i]=0;
            g[i]=0;
            sum[i]=0;
            a[i]=0;
        }
        ncnt=0;
        m=0;
        T=0;
        n=0;
    }
    inline int ID(int x) {
        return x <= T ? id1[x] : id2[n / x];
    }

    inline int calc(int x) {
        x%=mod;
        return( x * (x + 1)%mod*(2*x+1)%mod*Ny6%mod - 1+mod)%mod;
    }

    inline int f(int x) {
        return x;
    }

    inline void init() {
        T = sqrtl(n + 0.5)+100;
        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 (int 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 && (int)prime[i] * prime[i] <= a[j]; j++)
                g[j] = g[j] - prime[i]*prime[i]%mod * (g[ID(a[j] / prime[i])] - sum[i - 1]+mod)%mod,
                g[j]=(g[j]%mod+mod)%mod;
    }

    inline int solve(int x) {
        fff();
        if (x <= 1) return x;
        return n = x, init(), g[ID(n)];
    }

}

int Sum(int x){
    x%=mod;
    return x*(x+1)%mod*Ny2%mod;
}
int Sum2(int x){
    x%=mod;
    return x*(x+1)%mod*(x*2%mod+1)%mod*Ny6%mod;
}
int S(int x){
    return Min25_1::solve(x);
}
int S2(int x){
    return Min25_2::solve(x);
}
bool isp(int x){
    for(int i=2;i*i<=x;i++)if(x%i==0)return false;
    return true;
}
signed main()
{
    int n;cin>>n;
    int p1=(S(n)-S(n/2)+mod)%mod;
    int p2=(S2(n)-S2(n/2)+mod)%mod;
    int z=(Sum(n)-1+mod)%mod*((Sum(n)-1+mod)%mod)%mod;
    // cout<<"z="<<z<<" p1="<<p1<<" p2="<<p2<<endl;
    z=(z-(Sum(n)-1+mod)*p1%mod+mod-(Sum(n)-1-p1+mod+mod)%mod*p1%mod+mod)%mod;
    // cout<<"z="<<z<<endl;
    z=(z+p2)%mod;
    z=(z-(Sum2(n)-1)+mod)%mod;
    z=z*Ny2%mod;
    cout<<z;
    // int ans=0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 8ms

memory: 113048kb

input:

output:

result:

ok 1 number(s): "8"

Test #2:

score: 0

Accepted

time: 12ms

memory: 113016kb

input:

output:

result:

ok 1 number(s): "8"

Test #3:

score: 0

Accepted

time: 7ms

memory: 113020kb

input:

output:

result:

ok 1 number(s): "80"

Test #4:

score: 0

Accepted

time: 7ms

memory: 112948kb

input:

output:

result:

ok 1 number(s): "80"

Test #5:

score: 0

Accepted

time: 4ms

memory: 113016kb

input:

output:

result:

ok 1 number(s): "200"

Test #6:

score: 0

Accepted

time: 8ms

memory: 113020kb

input:

output:

result:

ok 1 number(s): "407"

Test #7:

score: 0

Accepted

time: 18ms

memory: 113012kb

input:

output:

result:

ok 1 number(s): "937"

Test #8:

score: 0

Accepted

time: 7ms

memory: 113088kb

input:

output:

result:

ok 1 number(s): "3224298"

Test #9:

score: 0

Accepted

time: 7ms

memory: 113140kb

input:

output:

21077222

result:

ok 1 number(s): "21077222"

Test #10:

score: 0

Accepted

time: 7ms

memory: 113004kb

input:

output:

57411585

result:

ok 1 number(s): "57411585"

Test #11:

score: 0

Accepted

time: 16ms

memory: 112984kb

input:

output:

605750829

result:

ok 1 number(s): "605750829"

Test #12:

score: 0

Accepted

time: 7ms

memory: 112948kb

input:

output:

509863120

result:

ok 1 number(s): "509863120"

Test #13:

score: 0

Accepted

time: 12ms

memory: 113004kb

input:

output:

311440260

result:

ok 1 number(s): "311440260"

Test #14:

score: 0

Accepted

time: 12ms

memory: 113024kb

input:

output:

102191845

result:

ok 1 number(s): "102191845"

Test #15:

score: 0

Accepted

time: 11ms

memory: 113156kb

input:

output:

300787918

result:

ok 1 number(s): "300787918"

Test #16:

score: 0

Accepted

time: 8ms

memory: 113048kb

input:

output:

505062591

result:

ok 1 number(s): "505062591"

Test #17:

score: 0

Accepted

time: 12ms

memory: 113016kb

input:

output:

181810798

result:

ok 1 number(s): "181810798"

Test #18:

score: 0

Accepted

time: 8ms

memory: 113140kb

input:

output:

716166793

result:

ok 1 number(s): "716166793"

Test #19:

score: 0

Accepted

time: 7ms

memory: 112984kb

input:

output:

753032272

result:

ok 1 number(s): "753032272"

Test #20:

score: 0

Accepted

time: 12ms

memory: 113036kb

input:

output:

874612082

result:

ok 1 number(s): "874612082"

Test #21:

score: 0

Accepted

time: 12ms

memory: 113052kb

input:

output:

68635874

result:

ok 1 number(s): "68635874"

Test #22:

score: 0

Accepted

time: 7ms

memory: 113096kb

input:

output:

862578797

result:

ok 1 number(s): "862578797"

Test #23:

score: 0

Accepted

time: 11ms

memory: 113020kb

input:

output:

231728766

result:

ok 1 number(s): "231728766"

Test #24:

score: 0

Accepted

time: 7ms

memory: 112948kb

input:

output:

106207351

result:

ok 1 number(s): "106207351"

Test #25:

score: 0

Accepted

time: 14ms

memory: 113092kb

input:

output:

580625063

result:

ok 1 number(s): "580625063"

Test #26:

score: 0

Accepted

time: 17ms

memory: 113076kb

input:

output:

790849562

result:

ok 1 number(s): "790849562"

Test #27:

score: 0

Accepted

time: 11ms

memory: 113044kb

input:

output:

856082142

result:

ok 1 number(s): "856082142"

Test #28:

score: 0

Accepted

time: 64ms

memory: 113004kb

input:

998244350

output:

539142456

result:

ok 1 number(s): "539142456"

Test #29:

score: 0

Accepted

time: 68ms

memory: 113000kb

input:

998244351

output:

730264865

result:

ok 1 number(s): "730264865"

Test #30:

score: 0

Accepted

time: 71ms

memory: 113020kb

input:

998244352

output:

326703895

result:

ok 1 number(s): "326703895"

Test #31:

score: 0

Accepted

time: 68ms

memory: 112936kb

input:

998244353

output:

326703895

result:

ok 1 number(s): "326703895"

Test #32:

score: 0

Accepted

time: 57ms

memory: 113092kb

input:

998244354

output:

730264864

result:

ok 1 number(s): "730264864"

Test #33:

score: 0

Accepted

time: 64ms

memory: 113088kb

input:

998244355

output:

539142451

result:

ok 1 number(s): "539142451"

Test #34:

score: 0

Accepted

time: 70ms

memory: 113096kb

input:

998244356

output:

751581014

result:

ok 1 number(s): "751581014"

Test #35:

score: 0

Accepted

time: 101ms

memory: 112888kb

input:

2165916141

output:

216013547

result:

ok 1 number(s): "216013547"

Test #36:

score: 0

Accepted

time: 135ms

memory: 113084kb

input:

3550627266

output:

318019384

result:

ok 1 number(s): "318019384"

Test #37:

score: 0

Accepted

time: 312ms

memory: 112864kb

input:

11640239920

output:

137498099

result:

ok 1 number(s): "137498099"

Test #38:

score: 0

Accepted

time: 386ms

memory: 113012kb

input:

16191777349

output:

991399721

result:

ok 1 number(s): "991399721"

Test #39:

score: 0

Accepted

time: 608ms

memory: 112956kb

input:

31326230483

output:

99981147

result:

ok 1 number(s): "99981147"

Test #40:

score: 0

Accepted

time: 632ms

memory: 113080kb

input:

32810385543

output:

284259680

result:

ok 1 number(s): "284259680"

Test #41:

score: 0

Accepted

time: 688ms

memory: 113080kb

input:

37368395332

output:

511468046

result:

ok 1 number(s): "511468046"

Test #42:

score: 0

Accepted

time: 733ms

memory: 113020kb

input:

40002331093

output:

282851705

result:

ok 1 number(s): "282851705"

Test #43:

score: 0

Accepted

time: 1205ms

memory: 113100kb

input:

82884464396

output:

767050832

result:

ok 1 number(s): "767050832"

Test #44:

score: 0

Accepted

time: 1348ms

memory: 112892kb

input:

96506992785

output:

31413975

result:

ok 1 number(s): "31413975"

Test #45:

score: 0

Accepted

time: 1385ms

memory: 112984kb

input:

99999999995

output:

456189842

result:

ok 1 number(s): "456189842"

Test #46:

score: 0

Accepted

time: 1381ms

memory: 113100kb

input:

99999999996

output:

516138273

result:

ok 1 number(s): "516138273"

Test #47:

score: 0

Accepted

time: 1399ms

memory: 113016kb

input:

99999999997

output:

136420410

result:

ok 1 number(s): "136420410"

Test #48:

score: 0

Accepted

time: 1387ms

memory: 112984kb

input:

99999999998

output:

841974696

result:

ok 1 number(s): "841974696"

Test #49:

score: 0

Accepted

time: 1387ms

memory: 113024kb

input:

99999999999

output:

164762165

result:

ok 1 number(s): "164762165"

Test #50:

score: 0

Accepted

time: 1369ms

memory: 113032kb

input:

100000000000

output:

627965619

result:

ok 1 number(s): "627965619"