LINK:DZY Loves Math
一道比较有意思的数论题 原谅我的智障多调了 40min.
可以简单的推式子推出 答案为 \(\sum{w=1}^n\frac{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;
- }
来源: http://www.bubuko.com/infodetail-3474382.html