https://www.luogu.org/problemnew/show/P3327
不会做。
去搜题解...为什么题解都用了一个奇怪的公式？太奇怪了啊。。。
公式是这样的：
$d(xy)=\sum_{i|x}\sum_{j|y}[(i,j)=1]$
证明：（转自：https://23613.blog.luogu.org/solution-p3327）
考虑一个质因子p，设x中p的指数为a，y中p的指数为b（指质因数分解结果中指数），那么根据因数个数定理，这个质因子对式子左边的贡献（指使得答案乘上的值）是a+b+1；在式子右边，要么i中p的指数为0且j中p的指数为1~b，要么j中p的指数为0且i中p的指数为1~a，要么i和j中p的指数均为0（为了保证i,j互质），所以p的贡献是(b+a+1)。那么左右两边就相等了...
没办法了，背公式吧...找不到别的做法
答案要求的式子ans可以化为$\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1]{\lfloor}\frac{n}{i}{\rfloor}{\lfloor}\frac{m}{j}{\rfloor}$
反演一下，得到$ans=\sum_{k=1}^m\mu(k)\sum_{i=1}^{{\lfloor}\frac{n}{k}{\rfloor}}\sum_{j=1}^{{\lfloor}\frac{m}{k}{\rfloor}}{\lfloor}\frac{n}{ik}{\rfloor}{\lfloor}\frac{m}{jk}{\rfloor}$（不妨设n<=m）
设$f(x)=\sum_{i=1}^x{\lfloor}\frac{x}{i}{\rfloor}$，这个显然可以n*sqrt预处理出来
$ans=\sum_{k=1}^m\mu(k)f({\lfloor}\frac{n}{k}{\rfloor})f({\lfloor}\frac{m}{k}{\rfloor})$
那么原式也可以简单的在一次询问sqrt的时间内求出
本以为就这样子A掉了，结果...T飞了
不管了。。O3开开A掉
网上找了一下，有一个方法卡常数：可以发现f函数是约数个数函数的前缀和，因此可以筛出约数个数然后直接前缀和，这样预处理就是O(n)的
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
ll prime[],len,ff[],mu[];
bool nprime[];
ll ans,n,m;
int main()
{
ll i,j,k,T;
mu[]=;
for(i=;i<=;i++)
{
if(!nprime[i]) prime[++len]=i,mu[i]=-;
for(j=;j<=len&&i*prime[j]<=;j++)
{
nprime[i*prime[j]]=;
if(i%prime[j]==) {mu[i*prime[j]]=;break;}
else mu[i*prime[j]]=-mu[i];
}
}
for(i=;i<=;i++) mu[i]+=mu[i-];
for(k=;k<=;k++)
{
for(i=;i<=k;i=j+)
{
j=min(k,k/(k/i));
ff[k]+=(j-i+)*(k/i);
}
}
//for(i=1;i<=10;i++) printf("%lld\n",ff[i]);
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
if(n>m) swap(n,m);
ans=;
for(i=;i<=n;i=j+)
{
j=min(n,min(n/(n/i),m/(m/i)));
ans+=(mu[j]-mu[i-])*ff[n/i]*ff[m/i];
}
printf("%lld\n",ans);
}
return ;
}
http://codeforces.com/contest/235/problem/E
是不是感觉非常像？
事实上，不仅式子像，结论也是一样的。。。好神奇啊
结论是：$d(xyz)=\sum_{i|x}\sum_{j|y}\sum_{k|z}[(i,j)=1][(j,k)=1][(i,k)=1]$
证明也是类似的；貌似可以推广到更高维(?没试过)
同样的，$ans=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c[(i,j)=1][(j,k)=1][(i,k)=1]{\lfloor}\frac{a}{i}{\rfloor}{\lfloor}\frac{b}{j}{\rfloor}{\lfloor}\frac{c}{k}{\rfloor}$
耶，我又不会了，反演嘛式子推不清楚，乱搞嘛搞不出来
到网上找，发现一个技巧：如果只是要求XXX=1，用$\sum_{d|k}\mu(d)=[k=1]$去代比直接反演更方便
有了这样一个做法：
枚举i，搞出所有可能的j,k（指与i互质且在范围内），分别放入数组aj,ak
那么就需要从aj,ak内分别取一个元素x,y，如果(x,y)==1则可以计算贡献
也就是要计算$\sum_{j{\in}aj}\sum_{k{\in}ak}[(j,k)=1]{\lfloor}\frac{b}{j}{\rfloor}{\lfloor}\frac{c}{k}{\rfloor}=\sum_{j{\in}aj}\sum_{k{\in}ak}\sum_{d|(j,k)}\mu(d){\lfloor}\frac{b}{j}{\rfloor}{\lfloor}\frac{c}{k}{\rfloor}$
考虑对每一个d统计贡献，复杂度n^2*log
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int prime[],len,mu[];
bool nprime[];
int a,b,c,mm;
unsigned ans,a1,n1,n2;
bool aj[],ak[];
int main()
{
int i,j,k,d;
mu[]=;
for(i=;i<=;i++)
{
if(!nprime[i]) prime[++len]=i,mu[i]=-;
for(j=;j<=len&&i*prime[j]<=;j++)
{
nprime[i*prime[j]]=;
if(i%prime[j]==) {mu[i*prime[j]]=;break;}
else mu[i*prime[j]]=-mu[i];
}
}
scanf("%d%d%d",&a,&b,&c);
mm=max({a,b,c});
for(i=;i<=a;i++)
{
a1=;
for(j=;j<=b;j++)
aj[j]=(__gcd(i,j)==);
for(k=;k<=c;k++)
ak[k]=(__gcd(i,k)==);
for(d=;d<=mm;d++)
{
n1=n2=;
for(j=d;j<=b;j+=d)
n1+=aj[j]*(b/j);
for(k=d;k<=c;k+=d)
n2+=ak[k]*(c/k);
a1+=n1*n2*mu[d];
}
ans+=a1*(a/i);
}
printf("%u",ans%);
return ;
}