OI小白,求调
查看原帖
OI小白,求调
515930
ioker楼主2021/10/21 21:06

RT,50ptsRT,50pts

#include<stdio.h>
#include<ctype.h>
#include<time.h>
#include<iostream>
#define int long long
const int inv=(19940418>>1),p=19940417,inv_=3323403;
using namespace std;
inline int read(){
  int n=0,m=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')m=-1;
    c=getchar();
  }
  while(isdigit(c)){
    n=(n<<1)+(n<<3)+c-'0';
    c=getchar();
  }
  return n*m;
}
int sum(int n){return 1ll*n*(n+1)%p*inv%p;}
int sum_(int n){return 1ll*n*(n+1)%p*(2*n+1)%p*inv_%p;}
signed main(){
  int n=read(),m=read(),ans1=1ll*n*n%p,ans2=1ll*m*m%p,ans3=0;
  if(n>m)n^=m^=n^=m;
  for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    ans1=(ans1-(sum(r)-sum(l-1)+p)%p*(n/l)%p+p)%p;
  }
  for(int l=1,r;l<=m;l=r+1){
    r=m/(m/l);
    ans2=(ans2-(sum(r)-sum(l-1)+p)%p*(m/l)%p+p)%p;
  }
  ans1%=p;
  ans2%=p;
  for(int l=1,r;l<=n;l=r+1){
    r=min(n/(n/l),m/(m/l));
    int a=(r-l+1)*n%p*m%p;
    int b=(sum(r)-sum(l-1)+p)%p*((n/l)*m%p+(m/l)*n%p)%p;
    int c=(sum_(r)-sum_(l-1)+p)%p*(n/l)%p*(m/l)%p;
    ans3=(ans3+a-b+c+p)%p;
  }
  cout<<(1ll*ans1*ans2%p-ans3+p)%p<<'\n';
  return 0;
}
2021/10/21 21:06
加载中...