LINK：DZY Loves Math
一道比较有意思的数论题 原谅我的智障多调了40min.
可以简单的推式子推出 答案为(sum_{w=1}^nfrac{n}{w}frac{m}{w}sum{x|w}mu(x)f(frac{w}{x}))
f函数定义和题目中一致。
考虑后面前缀和怎么求 发现光求f(x)复杂度都比较高。如果我们把f(x)求出再调和级数预处理 那得GG 1e7过不了log+根号
考虑考虑一下(mu)和f的这种形式肯定值有局限 设后面的东西为g(x) 不难发现g(x)只有三种取值。
不难证明当 x的质因子指数都相同时答案为((-1)^{k+1}).其余情况为0 特殊的当只有一个质因子的时候答案为1.
具体证明可以分析讨论x的质因子指数长啥样来讨论 或者 列举几个数字。O(n)预处理就能过辣。
const int MAXN=10000010;
int n,m,maxx,T,top;
int p[MAXN],v[MAXN],a[MAXN],b[MAXN],g[MAXN];
inline void prepare()
{
rep(2,maxx,i)
{
if(!v[i])
{
p[++top]=v[i]=b[i]=i;
a[i]=g[i]=1;
}
rep(1,top,j)
{
if(maxx/i<p[j])break;
int ww=i*p[j];
v[ww]=p[j];
if(v[i]==p[j])
{
a[ww]=a[i]+1;
b[ww]=b[i]*p[j];
int w1=ww/b[ww];
g[ww]=w1==1?1:(a[ww]==a[w1])?-g[w1]:0;
break;
}
else
{
a[ww]=1;b[ww]=p[j];
g[ww]=a[ww]==a[i]?-g[i]:0;
}
}
}
rep(1,maxx,i)g[i]+=g[i-1];
}
int main()
{
freopen("1.in","r",stdin);
get(T);maxx=10000000;prepare();
while(T--)
{
get(n);get(m);
if(n>m)swap(n,m);
ll w1,w2,ww,ans=0;
for(int i=1;i<=n;i=ww+1)
{
w1=n/i;w2=m/i;
ww=min(n/w1,m/w2);
ans=ans+(ll)(g[ww]-g[i-1])*w1*w2;
}
putl(ans);
}
return 0;
}