题目描述
求
输入格式
两个整数。
输出格式
一个整数表示答案的值。
题目解析
我们先不考虑的情况。由分配律原式可转化为
我们只需考虑
这一部分是经典问题,有
只有
种取值,分段求一下即可。
再来考虑我们。这一部分的答案应从上述推导的结果中减去,有
还是分段求即可。时间复杂度。
话说公式推起来不难,写起来真麻烦,到处模模模……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
/************************************************************** Problem: 2956 User: frank_c1 Language: C++ Result: Accepted Time:156 ms Memory:1276 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int mo=19940417; inline LL inc(LL x) {return (x*(x+1)/2)%mo;} inline LL sqr(LL x) { LL a=x,b=x+1,c=2*x+1; if(a%2==0) a/=2; else if(b%2==0) b/=2; else c/=2; if(a%3==0) a/=3; else if(b%3==0) b/=3; else c/=3; return (a*b%mo)*c%mo; } LL calc(LL n) { LL res=0,pos; for(LL i=1;i<=n;i=pos+1) { pos=n/(n/i); res=(res+(n/i)*(inc(pos)+mo-inc(i-1)))%mo; } return res; } LL solve(LL n,LL m) { LL res=0,pos; for(LL i=1;i<=min(n,m);i=pos+1) { pos=min(n/(n/i),m/(m/i)); res=(res+(n*(m/i)%mo)*(inc(pos)+mo-inc(i-1))%mo+(m*(n/i)%mo)*(inc(pos)+mo-inc(i-1))%mo+((mo-1)*(n/i)%mo)*((m/i)*(sqr(pos)+mo-sqr(i-1))%mo))%mo; } return ((min(n,m)*n%mo)*m%mo+mo-res)%mo; } int main() { LL n,m; read(n);read(m); LL res=((n*n%mo)-calc(n)+mo)*((m*m%mo)-calc(m)+mo)%mo; printf("%lld\n",(res+mo-solve(n,m))%mo); return 0; } |