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

fish_love_cat · 2025-07-13 10:01:02 · 题解

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

刻画合法三元组性质：

当 a<b，显然有 c=a，不合法。

于是 a\ge b。

当 b\mid a，显然有 c=0，不合法。

于是 b\nmid a。

对于任意 a,b 显然都有唯一的 c。

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

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

然后做完了。

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

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

#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;
}