题目描述

Description

　求

Input

第一行两个数n,m。

Output

一个整数表示答案mod 19940417的值

Sample Input

3 4

Sample Output

1

数据规模和约定

对于100%的数据n,m<=10^9。

题目分析

还需要用到
所以要用到6的逆元
分三部分分块求解 时间复杂度

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long n,m,ans;
long long niv=3323403ll,mod=19940417ll;
long long sum1,sum2,sum3;
long long calc(long long tmp)
{
    return (tmp*(tmp+1)%mod*(tmp*2+1)%mod)*niv%mod;
}
long long last;
int main()
{   
    scanf("%lld%lld",&n,&m);
    if(n>m) swap(n,m);
    for(long long tmp,i=1;i<=n;i=last+1)
    {
        last=(n/(n/i));
        tmp=(n*(last-i+1)%mod-(i+last)*(last-i+1)/2%mod*(n/i)%mod+mod)%mod;
        sum1=(sum1+tmp)%mod;
    }
    for(long long tmp,i=1;i<=m;i=last+1)
    {
        last=(m/(m/i));
        tmp=(m*(last-i+1)-(i+last)*(last-i+1)/2%mod*(m/i)%mod+mod)%mod;
        sum2=(sum2+tmp)%mod;
    }
    for(long long tmp,i=1;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        tmp=(last-i+1)*n%mod*m%mod+(n/i)*(m/i)%mod*((calc(last)-calc(i-1)+mod)%mod)%mod;
        tmp=(tmp-( (i+last)*(last-i+1)/2%mod*n%mod*(m/i)%mod + (i+last)*(last-i+1)/2%mod*m%mod*(n/i)%mod  )%mod+mod)%mod;
        sum3=(sum3+tmp)%mod;
    }
    printf("%lld",(sum1*sum2%mod-sum3%mod+mod)%mod);
    return 0;
}