【数論】モビウスの反転例題のまとめ

9003 ワード

指路ブログ:peng-ymモビウス反転

モビウス関数:

・(d=1)の場合、(mu(d)=1);・(d=prod_{i=1}^k p_i)かつ(p_i)が相互異素数である場合、(mu(d)=(-1)^k).(d)が任意の質量因子を含むべき乗が2以上である場合、関数値は0になります.・任意の正の整数(n)、(sum_{d|n}^{}mu(d)=[n=1])について.・任意の正の整数(n)、(sum_{d|n}^{}{frac{mu(d)}d}={frac{phi(n)}n})について.・線ふるいモビウス関数(順帯オーラ関数:

int pri[maxn+5],mu[maxn+5],phi[maxn];
void init()
{
    mu[1]=phi[1]=1;
    for(int i=2;i

モビウス

・F(n)とf(n)は非負の整数集合に定義された2つの関数であり、条件を満たす[F(n)=sum_{d|n}f(d)]では、[f(n)=sum_{d|n}μ(d)F(lfloorfrac ndrfloor)]この定理をモビウス反転定理と呼ぶ.モビウスの反転には別の形式があり,F(n)とf(n)が[F(n)=sum_{n|d}f(d)]を満たすと[f(n)=sum_{n|d}を押し出すことができる.μ(\frac dn)F(d)\]
例題
luoguP 2257 YYのGCD

題目説明:与えられたN,M,1<=x<=N,1<=y<=M,gcd(x,y)が質量数である(x,y)の

対を求める

入力フォーマット:第1行の1つの整数Tはデータ群数の次のT行を表し、各行の2つの正の整数はNを表し、M

を表す.

データ範囲:T=10000;N, M <= 10000000

出力フォーマット:T行、各行に1つの整数

指路ブログ:peng-ym YYのGCD

等価:(Ans=sum_{i=1}^nsum_{j=1}^m[gcd(x,y)=prim])

(f(d))を(gcd(i,j)=d)の個数、(F(n))を(gcd(i,j)=n)と(n)の倍数の個数、すなわち、[f(d)=sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d][F(n)=sum_{n|d}f(d)=lfloorfrac Nnrfloorlflflloorlfllorlfllorlfllorlfllorlflloor oorfrac Mnrfloor]モビウスにより反転[f(n)=sum_{n|d}mu(lfloorfrac dnrfloor)F(d)]

簡略化式:[Ans=sum_{pin prim}sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=p]]を(f(p))に代入する[begin{align*} Ans&=sum_{pin prim}f(p)\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\{align*}]列挙項目を変更します.列挙(lfloorfracdprfloor):[begin{align*} Ans&=sum_{pin prim}sum_{d=1}^{min(lfloorfracnprfloor,lfloorfracmp rfloor)}mu(d)F(dp)\\\\&=sum_{pin prim}sum_{d=1}^{min(lfloorfracnprfloor,lfloorfloorfloorfracnpfloor\\\\\floor\\\\\\\fracmprfloor)}mu(d)lfloorfrac nprfloorlfloorfrac mprfloorend{align*}]dpをT:[begin{align*}Ans&=sum_{T=1}^{min(n,m)}sum_{t|T,tin prim}mu(\lfloor\frac Tt\rfloor)\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\\& =\sum_{T=1}^{min(n,m)}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor(\sum_{t|T,t\in prim}\mu(\lfloor\frac Tt\rfloor)\;)\end{align*}\]

以降ブロック

を除去する.

コード:

#include
#define debug1 printf("!");
#define debug2 puts("#");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e7;
const int mod=6893911;
const int inf=0x3f3f3f3f;

templateinline void read(T&x)
{
    char c;
    while(!isdigit(c=getchar()));x=c-'0';
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-'0';
}

ll sum[maxn+5];
int mu_pfac[maxn+5];
int mu[maxn+5];
int pri[maxn+5],cnt;
inline void init()
{
    mu[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!pri[i])
        {
            pri[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=maxn;j++)
        {
            pri[i*pri[j]]=1;
            if(i%pri[j]==0)break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<=maxn;i++)
        for(int j=1;j<=cnt&&i*pri[j]<=maxn;j++)
            mu_pfac[i*pri[j]]+=mu[i];
    for(int i=1;i<=maxn;i++)
        sum[i]=sum[i-1]+(ll)mu_pfac[i];
}
inline ll solve(int n,int m)
{
    if(n>m)swap(n,m);
    ll ans=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
    }
    return ans;
}


int main()
{
    init();
    int T;
    read(T);
    while(T--)
    {
        int n,m;
        read(n);read(m);
        printf("%lld
",solve(n,m));
    }
}

luoguP3455 ZAP-Queries

題目説明:a,b,dを与えて、1<=x<=aを求めて、1<=y<=bでgcd(x,y)=dの(x,y)はどれだけの対

があります

入力フォーマット:第1行の1つの整数Tはデータ群数の次のT行を表し、各行の3つの正の整数はa,b,d

を表す.

データ範囲(1leq Tleq 5times 10^4,1leq dleq a,bleq 5times 10^4)

出力フォーマット:T行、各行に1つの整数

指路ブログ:peng-ym ZAP-Queries

等価:(Ans=sum_{i=1}^asum_{j=1}^b[gcd(x,y)=d])

(f(d))を(gcd(i,j)=d)の個数とし、(F(n))を(gcd(i,j)=n)と(n)の倍数の個数とする.すなわち、[f(d)=sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d][F(n)=sum_{n|d}f(d)=lfloorfracanfracanrfloorlflooo rlflooo rlflooo o o rlfloorlfloorlflooo o o rlfloorlfloorflrfrac bnrfloor]モビウスより反転:[f(n)=sum_{n|d}mu(lfloorfrac dnrfloor)F(d)]混同しないように題意のdをnに置き換え、(f(n))を代入する:[begin{align*} Ans&=f(n)\&=sum_{n|d}mu(lfloorfracdn rfloor)F(d)end{ align*}]列挙項を交換し、列挙(lfloorfracdn rfloor)を(t):[Ans=sum_{t=1}^{min(lfloorfracapfloorfracaploor,lfloorfloorfloorfloorfloorfloorfloorfloorfloorfloorfloorfloor\frac bdrfloor}mu(t)lfloorfrac a{td}rfloorlfloorfrac b{td}rfloor]

以降ブロック

を除去する.

コード:

#include
#define debug1 printf("!");
#define debug2 puts("#");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
const int mod=6893911;
const int inf=0x3f3f3f3f;

templateinline void read(T&x)
{
    char c;
    while(!isdigit(c=getchar()));x=c-'0';
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-'0';
}

ll smu[maxn+5];
int mu[maxn+5];
int pri[maxn+5],cnt;
inline void init()
{
    mu[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!pri[i])
        {
            pri[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=maxn;j++)
        {
            pri[i*pri[j]]=1;
            if(i%pri[j]==0)break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<=maxn;i++)smu[i]=smu[i-1]+(ll)mu[i];
}
inline ll solve(int a,int b,int d)
{
    if(a>b)swap(a,b);
    ll ans=0;
    for(int l=1,r;l<=a;l=r+1)
    {
        r=min(a/(a/l),b/(b/l));
        ans+=1ll*(a/(l*d))*(b/(l*d))*(smu[r]-smu[l-1]);
    }
    return ans;
}


int main()
{
    init();
    int T;
    read(T);
    while(T--)
    {
        int a,b,d;
        read(a);read(b);read(d);
        printf("%lld
",solve(a,b,d));
    }
}

luoguP 3327月数個と

題目説明:d(x)をxの約数とし、n,mを与え、[sum_{i=1}^nsum_{j=1}^m d(ij)]

を求める

入力フォーマット:最初の行の1つの整数Tはデータグループ数の次のT行を表し、各行の2つの正の整数n,m

データ範囲(1leq T,n,mleq 5times 10^4)

出力フォーマット:T行、各行に1つの整数

指路ブログ:peng-ym約数と

重要性:[d(ij)=sum_{x|i}sum_{y|i}[gcd(x,y)=1]]

等価(Ans=sum_{i=1}^nsum_{j=1}^msum_{x|i}sum_{y|i}[gcd(x,y)=1])

で[begin{align*}Ans&=sum_{i=1}^nsum_{j=1}^msum_{x|i}sum_{y|i}[gcd(x,y)=1]\&=sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|i}\sum_{d|gcd(x,y)}\mu(d)\\&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|i}\sum_{d=1}^{min(n,m)}\mu(d)*[d|gcd(x,y)]\;\;\;(改列挙d)\&=sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|i}[d|gcd(x,y)]\;\;\;(mu(d)を抽出)\end{align*}]は、列挙i,jおよびそれらの約数から列挙の約数に変更され、これらの約数の倍数の個数に直接乗じられる.各約数はその倍数に寄与するから:[begin{align*}Ans&=sum_{d=1}^{min(n,m)}mu(d)sum_{x=1}^nsum_{y=1}^m[d|gcd(x,y)]lfloorfrac nxrfloorlfloorfrac myrfloor&=sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac nd\rfloor}\sum_{y=1}^{\lfloor\frac md\rfloor}\lfloor\frac n{dx}\rfloor\lfloor\frac m{dy}\rfloor\;\;\;(列挙x,yを列挙dx,dyに変更)&=sum_{d=1}^{min(n,m)}\mu(d)(\sum_{x=1}^{\lfloor\frac nd\rfloor}\lfloor\frac n{dx}\rfloor)(\sum_{y=1}^{\lfloor\frac md\rfloor}\lfloor\frac m{dy}\rfloor)\;\;\;(lfloorfrac n{dx}rfloorはyに関係ないので繰り上げ可能)\end{align*}]

以降ブロック

を除去する.

コード:

#include
#define debug printf("#");
#define pb push_back
using namespace std;
typedef long long ll;
const int mod=998244353;
const int maxn=5e4+5;
const int inf=0x3f3f3f3f;

ll s[maxn];
//ll phi[maxn+5];
int mu[maxn+5];
int pri[maxn],p=0;
bool isp[maxn+5]={0};
inline void init()
{
//    phi[1]=1;
    mu[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!isp[i])
        {
            pri[++p]=i;
//            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=1;j<=p&&i*pri[j]<=maxn;j++)
        {
            isp[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
//                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
//            phi[i*pri[j]]=phi[i]*(pri[j]-1);
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=2;i<=maxn;i++)
    {
//        phi[i]+=phi[i-1];
        mu[i]+=mu[i-1];
    }
    for(int i=1;i<=50000;i++)
    {
        for(int l=1,r;l<=i;l=r+1)
        {
            r=i/(i/l);
            s[i]+=(r-l+1)*(i/l);
        }
    }
}

int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,up;
        ll ans=0;
        scanf("%d%d",&n,&m);
        up=min(n,m);
        for(ll l=1,r;l<=up;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans+=1ll*(mu[r]-mu[l-1])*s[n/l]*s[m/l];
        }
        printf("%lld
",ans);
    }
}

[Codility] MissingInteger

Hyperledger Fabric SDK例fabric-samples-「balance-transfer」の6「chaincodeの実行」