http://codeforces.com/contest/235/problem/E
远距离orz......rng_58
证明可以见这里（可能要翻墙才能看到）
还是copy一下证明吧：
记
$$f(a,b,c)=sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}sumlimits_{k=1}^{c}d(ijk)$$
和
$$g(a,b,c)=sumlimits_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor$$
我们先证明下面的等式：
$f(a,b,c)-f(a-1,b,c)-f(a,b-1,c)-f(a,b,c-1)+f(a-1,b-1,c)+f(a-1,b,c-1)+f(a,b-1,c-1)-f(a-1,b-1,c-1)$
$=g(a,b,c)-g(a-1,b,c)-g(a,b-1,c)-g(a,b,c-1)+g(a-1,b-1,c)+g(a-1,b,c-1)+g(a,b-1,c-1)-g(a-1,b-1,c-1)$
根据容斥原理，我们容易知道
$$等式左边=d(abc)$$
我们继续化简一下等式右边（可能有点长，不过很好理解）：
$g(a,b,c)-g(a-1,b,c)-g(a,b-1,c)-g(a,b,c-1)+g(a-1,b-1,c)+g(a-1,b,c-1)+g(a,b-1,c-1)-g(a-1,b-1,c-1)$
$=sumlimits_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}(left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor-left lfloor frac{a-1}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor-left lfloor frac{a}{i} ight floorleft lfloor frac{b-1}{j} ight floorleft lfloor frac{c}{k} ight floor-left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c-1}{k} ight floor+left lfloor frac{a-1}{i} ight floorleft lfloor frac{b-1}{j} ight floorleft lfloor frac{c}{k} ight floor+left lfloor frac{a-1}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c-1}{k} ight floor+left lfloor frac{a}{i} ight floorleft lfloor frac{b-1}{j} ight floorleft lfloor frac{c-1}{k} ight floor-left lfloor frac{a-1}{i} ight floorleft lfloor frac{b-1}{j} ight floorleft lfloor frac{c-1}{k} ight floor)$
因式分解得：
$=sumlimits_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}(left lfloor frac{a}{i} ight floor-left lfloor frac{a-1}{i} ight floor)(left lfloor frac{b}{i} ight floor-left lfloor frac{b-1}{i} ight floor)(left lfloor frac{c}{i} ight floor-left lfloor frac{c-1}{i} ight floor)$
容易知道，当且仅当$a\%i=0$时，$left lfloor frac{a}{i} ight floor-left lfloor frac{a-1}{i} ight floor=1$，其他时候为$0$。$left lfloor frac{b}{i} ight floor-left lfloor frac{b-1}{i} ight floor$和$left lfloor frac{c}{i} ight floor-left lfloor frac{c-1}{i} ight floor$也是如此。
很好，所以：
$$等式右边=|{(i,j,k)|gcd(i,j)=gcd(j,k)=gcd(i,k)=1且a\%i=b\%j=c\%k=0}|$$
$$（即满足gcd(i,j)=gcd(j,k)=gcd(i,k)=1且a\%i=b\%j=c\%k=0的三元组(i,j,k)的个数）$$
我们复习一下约数和定理：
记$P_i$为第$i$个质数，显然$P_1=2,P_2=3,P_3=5,P_4=7......$
对于质数$P_i$，记$x_i$是满足$a\%P_i^{x_i}=0$的最大数。类似地，记$y_i$是满足$b\%P_i^{y_i}=0$的最大数，记$z_i$是满足$c\%P_i^{z_i}=0$的最大数。
根据约数和定理，$d(abc)=prodlimits_{i=1}^{oo}(x_i+y_i+z_i+1)$
我们回过头来看我们的等式的右边：
$$等式右边=|{(i,j,k)|gcd(i,j)=gcd(j,k)=gcd(i,k)=1且a\%i=b\%j=c\%k=0}|$$
$$（即满足gcd(i,j)=gcd(j,k)=gcd(i,k)=1且a\%i=b\%j=c\%k=0的三元组(i,j,k)的个数）$$
我们试着构造出这个集合。
我们先将三元组$(i,j,k)$中的$i,j,k$分别质因数分解：
$i=P_1^{i_1} imes P_2^{i_2} imes P_3^{i_3} imes P_4^{i_4}......$
$j=P_1^{j_1} imes P_2^{j_2} imes P_3^{j_3} imes P_4^{j_4}......$
$k=P_1^{k_1} imes P_2^{k_2} imes P_3^{k_3} imes P_4^{k_4}......$
我们先考虑$P_1和i,j,k的质因子P_1的幂P_1^{i_1},P_1^{j_1},P_1^{k_1}$
因为$gcd(i,j)=gcd(j,k)=gcd(i,k)=1且a\%i=b\%j=c\%k=0$
所以三元组$(i_1,j_1,k_1)$总共有$x_1+y_1+z_1+1$种：
$(0,0,0)$，有1种
$(1,0,0),(2,0,0),(3,0,0),...,(x_1,0,0)$，有$x_1$种
$(0,1,0),(0,2,0),(0,3,0),...,(0,y_1,0)$，有$y_1$种
$(0,0,1),(0,0,2),(0,0,3),...,(0,0,z_1)$，有$z_1$种
类似地，三元组$(i_2,j_2,k_2)$有$x_2+y_2+z_2+1$种，三元组$(i_3,j_3,k_3)$有$x_3+y_3+z_3+1$种......
根据乘法原理，所以恰好就是$prodlimits_{i=1}^{oo}(x_i+y_i+z_i+1)$
又因为$等式左边=d(abc)=prodlimits_{i=1}^{oo}(x_i+y_i+z_i+1)=等式右边$
所以
$f(a,b,c)-f(a-1,b,c)-f(a,b-1,c)-f(a,b,c-1)+f(a-1,b-1,c)+f(a-1,b,c-1)+f(a,b-1,c-1)-f(a-1,b-1,c-1)$
$=g(a,b,c)-g(a-1,b,c)-g(a,b-1,c)-g(a,b,c-1)+g(a-1,b-1,c)+g(a-1,b,c-1)+g(a,b-1,c-1)-g(a-1,b-1,c-1)$
很好，我们已经证明了这个等式了。
然后用简单的数学归纳法，我们可以得到
$$f(a,b,c)=g(a,b,c)$$
所以
$sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}sumlimits_{k=1}^{c}d(ijk)=sumlimits_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor$
好神奇。。。。。。
而且这东西还能推广到任意维：
$sumlimits_{i=1}^{a}d(i)=sumlimits_{}left lfloor frac{a}{i} ight floor$
$sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}d(ij)=sumlimits_{gcd(i,j)=1}left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floor$
$sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}sumlimits_{k=1}^{c}d(ijk)=sumlimits_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor$
......
先看一道题放松一下。
好，回到本题。
先介绍一种比较简单的超时的方法。
记$g(x,y)=sumlimits_{i=1}^{x}sumlimits_{j=1}^{y}d(ij)$
我们可以在$O(sqrt{N})$的时间内完成。
记$s(n,r)=sumlimits_{i=1}^{r}d(in)$
容易知道$s(n,r)=g(n,r)-g(n-1,r)$，所以也可以在$O(sqrt{N})$的时间完成。
那么原问题就是：
$$sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}sumlimits_{k=1}^{c}d(ijk)=sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}s(ij,c)$$
直接枚举$i$和$j$，然后算$s(ij,c)$，时间复杂度是$O(N^{frac{5}{2}})$。
好吧，这种方法是超时。
2015.11.12
经过wck大神的提点，终于A这道题了。
$sumlimits_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}left lfloor frac{a}{i} ight floorleft lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor$
$=sumlimits_{i}left lfloor frac{a}{i} ight floorsumlimits_{(i,j)=1}sumlimits_{(i,k)=1}left lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floor[(j,k)==1]$
$=sumlimits_{i}left lfloor frac{a}{i} ight floorsumlimits_{(i,j)=1}sumlimits_{(i,k)=1}left lfloor frac{b}{j} ight floorleft lfloor frac{c}{k} ight floorsumlimits_{d|j,d|k}mu (d)$
$=sumlimits_{i}left lfloor frac{a}{i} ight floorsumlimits_{d}mu (d)sumlimits_{d|j,(i,j)=1}left lfloor frac{b}{j} ight floor sumlimits_{d|k,(i,k)=1}left lfloor frac{c}{k} ight floor$
$记j=dj',k=dk',则：$
$sumlimits_{i}left lfloor frac{a}{i} ight floorsumlimits_{d}mu (d)sumlimits_{(i,dj')=1}left lfloor frac{b}{dj'} ight floor sumlimits_{(i,dk')=1}left lfloor frac{c}{dk'} ight floor$
我们先枚举$i$和$d$，然后分别枚举求$sumlimits_{(i,dj')=1}left lfloor frac{b}{dj'} ight floor$ 和 $sumlimits_{(i,dk')=1}left lfloor frac{c}{dk'} ight floor$，我们枚举的次数只是是$b/d$和$c/d$
所以其实计算的次数只是$a*(b/1+b/2+...+b/b)<ablogb$，不超时。
#include<cstdio> #include<cstdlib> #include<iostream> #include<fstream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<utility> #include<set> #include<bitset> #include<vector> #include<functional> #include<deque> #include<cctype> #include<climits> #include<complex> //#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> PII; typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a)) #define mmcy(a,b) memcpy(a,b,sizeof(a)) #define fill(a,l,r,v) fill(a+l,a+r+1,v) #define re(i,a,b) for(i=(a);i<=(b);i++) #define red(i,a,b) for(i=(a);i>=(b);i--) #define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++) #define fi first #define se second #define m_p(a,b) make_pair(a,b) #define p_b(a) push_back(a) #define SF scanf #define PF printf #define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;} template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;} template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} inline int sgn(DB x){if(abs(x)<1e-9)return 0;return(x>0)?1:-1;} const DB Pi=acos(-1.0); int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } const int maxn=2000; const LL MOD=1073741824; int a,b,c; LL ans; int flag[maxn+100],cnt,prime[maxn+100],mul[maxn+100]; void prepare(int n) { int i,j; flag[1]=1;mul[1]=1; re(i,2,n) { if(!flag[i])prime[++cnt]=i,mul[i]=-1; for(j=1;j<=cnt && prime[j]*i<=n;j++) { flag[prime[j]*i]=1; if(i%prime[j]==0){mul[i*prime[j]]=0;break;}else mul[i*prime[j]]=-mul[i]; } } } int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int main() { freopen("CF235E.in","r",stdin); freopen("CF235E.out","w",stdout); int i; a=gint();b=gint();c=gint(); if(b<c)swap(b,c); prepare(b); int d,jp,kp; re(i,1,a) re(d,1,b)if(mul[d]!=0 && gcd(i,d)==1) { LL rj=0,rk=0; for(jp=1;d*jp<=b;jp++)if(gcd(i,jp)==1)(rj+=b/(d*jp))&=(MOD-1); for(kp=1;d*kp<=c;kp++)if(gcd(i,kp)==1)(rk+=c/(d*kp))&=(MOD-1); LL res=(a/i); (res*=mul[d])&=(MOD-1); (res*=rj)&=(MOD-1); (res*=rk)&=(MOD-1); (ans+=res)&=(MOD-1); } cout<<ans<<endl; return 0; }