题解：AT_abc414_e [ABC414E] Count A%B=C

简单题。

考虑单步容斥，把求满足条件个数看成所有不考虑条件1中

c\ge1

的个数减去

c=0

的个数。

本质上可以拆成一个等差数列减去求

2

到

n

每个数除了自己的因子之和。

要求

2

到

n

每个数除了自己的因子之和，可以用数论分块来做，时间复杂度可以保证在根号级别。

注意取模的问题，我为了图省事就最后再取的模。

赛时代码有点丑。

CPP

#include<bits/stdc++.h>
#define int __int128

using namespace std;

const int mod=998244353;

int n;
int ans;
int tot;

inline void read(int& a) {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
    }
    a = s * w;
}

void write(int x) {
    if (x < 0) {
    x = -x;
    putchar('-');
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

signed main()
{
    read(n);
    if(n==1)    return cout<<0<<endl,0;
    if(n==2)    return cout<<0<<endl,0;
    if(n==3)    return cout<<1<<endl,0;
    ans=(n+1)*((n-2))/2;
    tot=-n-1;
    for(int l=1,r;l<=n;l=r+1)
    {
        int d=n/l;
        r=n/d;
        tot+=d*(r-l+1);
    }
    cout<<(ans-tot)%mod<<endl;
    return 0;
}

题解：AT_abc414_e [ABC414E] Count A%B=C

文章操作

相关推荐

评论

题解：AT_abc414_e [ABC414E] Count A%B=C