QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#451258#8761. 另一个计数问题tarjenWA 142ms113092kbC++204.0kb2024-06-23 01:03:232024-06-23 01:03:24

Judging History

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

  • [2024-06-23 01:03:24]
  • 评测
  • 测评结果：WA
  • 用时：142ms
  • 内存：113092kb
查看
  • [2024-06-23 01:03:23]
  • 提交

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) {
        return x * (x + 1)%mod*Ny2%mod - 1;
    }

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

    inline void init() {
        T = sqrt(n + 0.5)+10;
        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) {
        return x * (x + 1)%mod*(2*x+1)%mod*Ny6%mod - 1;
    }

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

    inline void init() {
        T = sqrt(n + 0.5)+10;
        for (int i = 2; i <= T; i++) {
            if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = (sum[ncnt - 1] + i*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]*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+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)*(Sum(n)-1)%mod;
    // cout<<"z="<<z<<" p1="<<p1<<" p2="<<p2<<endl;
    z=(z-(Sum(n)-1)*p1%mod-(Sum(n)-1-p1)*p1%mod+2*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: 112968kb

input:

4

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 3ms
memory: 113068kb

input:

5

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 0
Accepted
time: 10ms
memory: 112964kb

input:

6

output:

80

result:

ok 1 number(s): "80"

Test #4:

score: 0
Accepted
time: 7ms
memory: 113000kb

input:

7

output:

80

result:

ok 1 number(s): "80"

Test #5:

score: 0
Accepted
time: 13ms
memory: 113020kb

input:

8

output:

200

result:

ok 1 number(s): "200"

Test #6:

score: 0
Accepted
time: 7ms
memory: 112892kb

input:

9

output:

407

result:

ok 1 number(s): "407"

Test #7:

score: 0
Accepted
time: 11ms
memory: 112976kb

input:

10

output:

937

result:

ok 1 number(s): "937"

Test #8:

score: 0
Accepted
time: 12ms
memory: 112968kb

input:

79

output:

3224298

result:

ok 1 number(s): "3224298"

Test #9:

score: 0
Accepted
time: 11ms
memory: 113008kb

input:

123

output:

21077222

result:

ok 1 number(s): "21077222"

Test #10:

score: 0
Accepted
time: 7ms
memory: 113036kb

input:

158

output:

57411585

result:

ok 1 number(s): "57411585"

Test #11:

score: 0
Accepted
time: 4ms
memory: 113072kb

input:

285

output:

605750829

result:

ok 1 number(s): "605750829"

Test #12:

score: 0
Accepted
time: 7ms
memory: 113064kb

input:

355

output:

509863120

result:

ok 1 number(s): "509863120"

Test #13:

score: 0
Accepted
time: 11ms
memory: 112884kb

input:

484

output:

311440260

result:

ok 1 number(s): "311440260"

Test #14:

score: 0
Accepted
time: 7ms
memory: 112972kb

input:

520

output:

102191845

result:

ok 1 number(s): "102191845"

Test #15:

score: 0
Accepted
time: 16ms
memory: 112972kb

input:

706

output:

300787918

result:

ok 1 number(s): "300787918"

Test #16:

score: 0
Accepted
time: 12ms
memory: 112896kb

input:

747

output:

505062591

result:

ok 1 number(s): "505062591"

Test #17:

score: 0
Accepted
time: 11ms
memory: 113036kb

input:

784

output:

181810798

result:

ok 1 number(s): "181810798"

Test #18:

score: 0
Accepted
time: 12ms
memory: 113060kb

input:

76879

output:

716166793

result:

ok 1 number(s): "716166793"

Test #19:

score: 0
Accepted
time: 7ms
memory: 112988kb

input:

209295

output:

753032272

result:

ok 1 number(s): "753032272"

Test #20:

score: 0
Accepted
time: 4ms
memory: 113064kb

input:

220895

output:

874612082

result:

ok 1 number(s): "874612082"

Test #21:

score: 0
Accepted
time: 8ms
memory: 113000kb

input:

243390

output:

68635874

result:

ok 1 number(s): "68635874"

Test #22:

score: 0
Accepted
time: 11ms
memory: 113000kb

input:

414767

output:

862578797

result:

ok 1 number(s): "862578797"

Test #23:

score: 0
Accepted
time: 15ms
memory: 112976kb

input:

431662

output:

231728766

result:

ok 1 number(s): "231728766"

Test #24:

score: 0
Accepted
time: 15ms
memory: 112892kb

input:

521130

output:

106207351

result:

ok 1 number(s): "106207351"

Test #25:

score: 0
Accepted
time: 4ms
memory: 112948kb

input:

668419

output:

580625063

result:

ok 1 number(s): "580625063"

Test #26:

score: 0
Accepted
time: 11ms
memory: 112940kb

input:

700378

output:

790849562

result:

ok 1 number(s): "790849562"

Test #27:

score: 0
Accepted
time: 12ms
memory: 112936kb

input:

965876

output:

856082142

result:

ok 1 number(s): "856082142"

Test #28:

score: 0
Accepted
time: 66ms
memory: 112976kb

input:

998244350

output:

539142456

result:

ok 1 number(s): "539142456"

Test #29:

score: 0
Accepted
time: 60ms
memory: 112884kb

input:

998244351

output:

730264865

result:

ok 1 number(s): "730264865"

Test #30:

score: 0
Accepted
time: 59ms
memory: 113092kb

input:

998244352

output:

326703895

result:

ok 1 number(s): "326703895"

Test #31:

score: 0
Accepted
time: 81ms
memory: 113072kb

input:

998244353

output:

326703895

result:

ok 1 number(s): "326703895"

Test #32:

score: 0
Accepted
time: 73ms
memory: 113076kb

input:

998244354

output:

730264864

result:

ok 1 number(s): "730264864"

Test #33:

score: 0
Accepted
time: 68ms
memory: 112972kb

input:

998244355

output:

539142451

result:

ok 1 number(s): "539142451"

Test #34:

score: 0
Accepted
time: 61ms
memory: 113036kb

input:

998244356

output:

751581014

result:

ok 1 number(s): "751581014"

Test #35:

score: 0
Accepted
time: 99ms
memory: 113052kb

input:

2165916141

output:

216013547

result:

ok 1 number(s): "216013547"

Test #36:

score: -100
Wrong Answer
time: 142ms
memory: 112884kb

input:

3550627266

output:

694331946

result:

wrong answer 1st numbers differ - expected: '318019384', found: '694331946'
English 繁體中文 简体中文

服务器时间: 2025-01-21 11:25:16 | 开源项目