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

整除分块板子，甚至不需要推导。

刻画合法三元组性质：

当

a<b

，显然有

c=a

，不合法。

于是

a\ge b

。

当

b\mid a

，显然有

c=0

，不合法。

于是

b\nmid a

。

对于任意

a,b

显然都有唯一的

c

。

满足限制一的组数是可以直接算的。

然后违反限制二的组数可以整除分块一下算出来。

然后做完了。

甚至把 UVA11526 粘过来改改就行。

样例三被卡精度的话记得开 __int128。

CPP

#include<bits/stdc++.h>
#define int __int128
#define mod 998244353ll
using namespace std;
int read(){
    int sum=0,fish=1;
    char c=getchar_unlocked();
    while((c<'0'||c>'9')&&c!='-')c=getchar_unlocked();
    if(c=='-')fish=-1,c=getchar_unlocked();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=getchar_unlocked();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x<10)putchar_unlocked(x+'0');
    else print(x/10),putchar_unlocked(x%10+'0');
}
void solve(){
    int n=read();
    int ans=0;
    int sq=sqrt((long long)n);
    for(int i=1;i<=sq;i++)
    ans+=n/i%mod,ans%=mod;
    ans*=2;ans%=mod;
    ans-=sq*sq%mod;ans=(ans+mod)%mod;
    print(((1ll+n)%mod*n%mod*499122177ll%mod-ans+mod)%mod);
}
signed main(){
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

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

文章操作

相关推荐

评论

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