锐客网

  1. 首页 > it技术 > >

My|3309: DZY Loves Math 莫比乌斯反演

mycode

令 F(i) 表示 i 所含质因子最大幂指数， f(i) 表示 gcd(x,y)=i 的数对 (x,y) 的数量，然后莫比乌斯反演得到下式：

Ans=∑T=1n?nT??mT?∑d∣TF(d)μ(Td)
令 G(T)=∑d∣TF(d)μ(Td)，然后我们大力讨论一下。
首先设 T=Px11×Px22×..×Pxkk,d==Py11×Py22×..×Pykk。
要使 μ(Td)≠0，必须满足 yi=xi或者 yi=xi?1。
令 a=Max1≤i≤k(xi)，则 F(d)=a或 a?1。
假设 T中一共有 q个质因子的指数为 a。
【My|3309: DZY Loves Math 莫比乌斯反演】一、当 q=k 时，
① f(d)=a 时

∑f(d)=af(d)μ(Td)=a×∑f(d)=aμ(Td)=a×∑i=1k(?1)k?iCik=a×(?1)k+1
② f(d)=a?1时
∑f(d)=a?1f(d)μ(Td)=(a?1)×∑f(d)=a?1μ(Td)=(a?1)×(?1)k
所以当 q=k时， G(T)=a×(?1)k+1+(a?1)×(?1)k=(?1)k+1
二、当 q ① f(d)=a时
∑f(d)=af(d)μ(Td)=a×∑f(d)=aμ(Td)=a×∑i=1q(?1)q?iCiq×∑j=0k?q(?1)jCjk?q=0
② f(d)=a?1时
∑f(d)=a?1f(d)μ(Td)=(a?1)×∑f(d)=a?1μ(Td)=(a?1)×(?1)q×∑j=0k?q(?1)jCjk?q=0
所以当 q 知道这些，我们可以线筛的时候记录一下最小质因子出现的次数和除去最小质因子 px11后的数，然后判断幂指数是否相等。

#include #include #define ll long long #define MAXN 10000005 using namespace std; int prime[MAXN],t[MAXN],last[MAXN]; ll g[MAXN]; bool flag[MAXN]; inline ll read() { ll a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar(); } while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar(); } return a*f; } inline void prepare() { for (int i=2; im) swap(n,m); printf("%lld\n",solve(n,m)); } return 0; }

    推荐阅读


    上一篇：ObjectAnimator平移并透明动画

    下一篇：QT5 设置开机动态启动画面