Description
求 ∑i=1a∑j=1b∑k=1cd(ijk),a,b,c≤2000
Input
三个整数 a,b,c(1≤a,b,c≤2000)
Output
输出结果模 1073741824
Sample Input
2 2 2
Sample Output
20
Solution
首先证明两个结论:
1 . d(mn)=∑i|m∑j|n[(i,j)=1]
设 m=pa11pa22...paxx,n=pb11pb22...pbxx
对 mn 的任一正因子 l ,假设 l=pc11pc22...pcxx ,则有 0≤ci≤ai+bi
令 s=pd11pd22...pdxx , t=pe11pe22...pexx ,其中 di={ci0ci≤aici>ai , ei={0ci?aici≤aici>ai
则有 (s,t)=1,s|m,t|n ,且显然该分解唯一
反之,如果 s,t 满足 (s,t)=1,s|m,t|n ,令 ci=?????di0ai+eidi≠0di=0,ei=0di=0,ei≠0 ,则 pc11pc22...pcxx|mn
显然该表示唯一,综上结论成立
2 . d(rst)=∑i|r∑j|s∑k|t[(i,j)=1][(i,k)=1][(j,k)=1]
d(rst)=∑i|r∑j|st[(i,j)=1]=∑i|s∑j|s∑k|t[(i,jk)=1][(j,k)=1]=∑i|r∑j|s∑k|t[(i,j)=1][(i,k)=1][(j,k)=1]
进而有
∑i=1a∑j=1b∑k=1cd(ijk) ====∑r=1a∑s=1b∑t=1c∑i|r∑j|s∑k|t[(i,j)=1][(i,k)=1][(j,k)=1]∑i=1a∑j=1b∑k=1c?ai??bj??ck?[(i,j)=1][(i,k)=1][(j,k)=1]∑i=1a∑j=1b∑k=1c?ai??bj??ck?[(i,j)=1][(i,k)=1]∑d|(j,k)μ(d)∑i=1a?ai?∑d=1min(b,c)μ(d)∑j=1?bd??bjd?[(i,jd)=1]∑k=1?cd??ckd?[(i,kd)=1]
预处理 gcd(i,j)和 mu(d),枚举 a,d,时间复杂度 O(n2log n)
【Code|CodeForces 235 E.Number Challenge(莫比乌斯反演+数论)】Code
#include
#include
#include
#include
#include
#include
#include
#include
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope(分治+NTT)
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally