2956: 模积和 乘法逆元 取模

2019-04-14 16:22发布

站内文章 / 模拟电子
11319 0 1408
建议直接开long long，否则各种强制转换类型可能会出问题。。我因为这调了好久，小数据拍的飞起大数据各种跪。。
公式见hzwer
bzoj题目描述坑。。其实还是挺简单的，分开计算就好了。。 #include #include #define ll long long #define p 19940417 #define ine2 9970209 #define ine6 3323403 using namespace std; ll n,m; ll calc(ll k,ll n) { ll tmp=0; for (ll i=1,pos=0;i<=k;i=pos+1) { pos=min(n/(n/i),k); (tmp+=(n/i)%p*(((pos+1)*(pos)%p*ine2%p-(i-1)*i%p*ine2%p+p)%p)%p)%=p; } return (tmp+p)%p; } ll calc0(ll n,ll m) { ll tmp=0; for (ll i=1,pos=0;i<=n;i=pos+1) { pos=min(n/(n/i),m/(m/i)); (tmp+=(n/i)*(m/i)%p*((pos*(pos+1)%p*(pos*2+1)%p*ine6%p-(i-1)*i%p*(i*2-1)%p*ine6%p+p)%p)%p)%=p; } return (tmp+p)%p; } int main() { scanf("%lld%lld",&n,&m); if (n>m) swap(n,m); ll t1=calc(n,n),t2=calc(m,m),t3=calc(n,m),t4=calc0(n,m); ll ans=((((ll)n*n%p-t1+p)%p)*(((ll)m*m%p-t2+p)%p)%p-((ll)n*n%p*m%p-(ll)t1*m%p-(ll)t3*n%p+t4%p+p*10)%p+p)%p; cout << ans << endl; return 0; }

热门文章