精华内容
下载资源
问答
  • caioj1280【莫比乌斯反演模板题】GCD
    2017-11-27 13:33:00

    题目传送门
    那么在T了那么久之后,终于迎来了提高组前因为种种原因未能按计划搞定的数论大军。而首当其冲的便是这啥莫比乌斯反演。话说第一次见到这名字还是莫比乌斯环。不知有没有人还有印象。好了,废话一大堆,切入正题。
    【前言】
    各位同学,如果你们想学这个貌似高深的算法,请先学习完caioj1157 线性筛选函数
    【题意】
    对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数,保证所有数据中a和c一定等于1。 注意:2,3和3,2是一种情况
    【输入格式】
    第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k,都小于等于10000
    【输出格式】
    共n行,每行一个整数表示满足要求的数对(x,y)的个数
    【样例输入】
    2
    1 3 1 5 1
    1 11014 1 14409 9
    【样例输出】
    9
    736427
    自认为下边儿写的很清楚了。其实里边涉及到莫比乌斯函数,也就是下文说的U数组,具体如何与公式结合推倒呢……我也不会。别喷,都是因为连负责这啥鬼专题的lmy大佬自己也不会……实力强人却懒的要死……好了不吐槽了。代码来也!

    //制作人:陈保良
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    /*
    公式:
    (1)约数和公式
    当n%d==0 && n>=1时
    设F(n)=sigmaG(d)
    G(n)=sigmaU(d)F(n/d)
    (2)倍数和公式
    当n%d==0 && n>=1时
    设F(d)=sigmaG(n)
    G(d)=sigmaU(n/d)F(n)
    这题中
    1<=x<=b,1<=y<=d
    F(t)表示有几个情况满足gcd(x,y)%t==0
    G(t)表示有几个情况满足gcd(x,y)==t
    所以当n%d==0(n是d的倍数) && n>=1时
    有F(d)=sigmaG(n)
    G(d)=sigmaU(n/d)F(n)
    即倍数和公式
    题目要求求满足gcd(x,y)==k的情况总数
    因为k是xy的最大公约数
    所以有gcd(x/k,y/k)==1,也就是G(1)
    所以题目由问F(k)转换为G(k)转换为G(1)啦!!!
    那么代入公式得G(1)=sigmaU(n/1)F(n)
    即G(1)=sigmaU(n)F(n)
    而是1的倍数的……不是所有数吗?!
    那么怎么找所有的F(i)呢
    再回头看F(t)表示gcd(x,y)%t==0
    而仅有x和y都是t的倍数时才能满足上式
    因此得F(t)=(x/t)*(y/t)
    因为xy的范围给出了,在题中就是F(t)=(b/t)*(d/t)
    代入回前式得G(1)=sigmaU(n)*(b/t)*(d/t)
    但题目也有强调2,33,2是同一种情况
    于是我们使b恒小于等于d
    那么显然多出的重复部分一定在较小的一块,也就是1<=x<=b,1<=y<=b这一块
    即G(1)=sigmaU(n)*(b/t)*(b/t)
    但是里边也有一半是对的
    于是最后的式子终于出来了G(1)=sigmaU(n)*(b/t)*(d/t)-sigmaU(n)*(b/t)*(b/t)/2
    然后让我们去枚举t求出答案吧!!
    */
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    int pr,prime[1300],U[11000];
    bool v[11000];
    void get_Mobius()
    {
        pr=0;
        U[1]=1;
        memset(v,1,sizeof(v));
        for(int i=2;i<=10000;i++)
        {
            if(v[i])
            {
                prime[++pr]=i;
                U[i]=-1;
            }
            for(int j=1;j<=pr && i*prime[j]<=10000;j++)
            {
                v[i*prime[j]]=0;
                if(i%prime[j]==0)
                {
                    U[i*prime[j]]=0;
                    break;
                }
                else U[i*prime[j]]=-U[i];
            }
        }
    }
    int main()
    {
        int t,a,b,c,d,k,s1,s2;
        get_Mobius();
        t=read();
        while(t--)
        {
            a=read();b=read();c=read();d=read();k=read();
            if(k==0){printf("0\n");continue;}
            b/=k;d/=k;
            if(b>d)swap(b,d);
            s1=s2=0;
            for(int i=1;i<=b;i++)s1+=U[i]*(b/i)*(d/i);
            for(int i=1;i<=b;i++)s2+=U[i]*(b/i)*(b/i);
            printf("%d\n",s1-s2/2);
        }
        return 0;
    }

    祝真的有兴趣看到这里的童鞋门顺利AC并成功掌握这门神奇至极的算法!

    更多相关内容
  • #include <bits/stdc++.h> #define FOR(i,s,t) for(int i=(s);i<=(t);i++) #define ROF(i,s,t) for(int i=(s);i>=(t);i--) #define pb push_back #define mp make_pair #define eb emplace_back #...

     

    #include <bits/stdc++.h>
    #define FOR(i,s,t) for(int i=(s);i<=(t);i++)
    #define ROF(i,s,t) for(int i=(s);i>=(t);i--)
    #define pb push_back
    #define mp make_pair
    #define eb emplace_back
    #define fi first
    #define se second
    #define endl '\n'
    using namespace std;
    typedef unsigned long long ull;
    typedef long long ll;
    const int maxn = 5e4 + 6;
    const ll mod = 1e9 + 7;
    const int inf = 0x3f3f3f3f;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    int readInt(){
        int x=0;
        bool sign=false;
        char c=getchar();
        while(!isdigit(c)){
            sign=c=='-';
            c=getchar();
        }
        while(isdigit(c)){
            x=x*10+c-'0';
            c=getchar();
        }
        return sign?-x:x;
    }
    ll readLong(){
        ll x=0;
        bool sign=false;
        char c=getchar();
        while(!isdigit(c)){
            sign=c=='-';
            c=getchar();
        }
        while(isdigit(c)){
            x=x*10+c-'0';
            c=getchar();
        }
        return sign?-x:x;
    }
    string readString(){
        string s;
        char c=getchar();
        while(isspace(c)){
            c=getchar();
        }
        while(!isspace(c)){
            s+=c;
            c=getchar();
        }
        return s;
    }
    
    int mu[maxn+1], vis[maxn+1], summu[maxn+1];
    vector <int> prime;
    
    void getPrime(){
        mu[1] = 1;
        FOR(i,2,maxn){
            if (!vis[i]) {
                prime.pb(i);
                mu[i] = -1;
            }
            for(int j = 0; j < prime.size() && i * prime[j] < maxn;j++){
                vis[i * prime[j]] = 1;
                if (i % prime[j] == 0) {
                    mu[i * prime[j]] = 0;
                    break;
                }
                mu[i * prime[j]] = - mu[i];
            }
        }
    }
    
    int a, b, c, d, k;
    
    ll solve(ll n, ll m){
        if (n > m) swap(n, m);
        ll res = 0;int pos = 0;
        for(int i = 1; i <= n; i = pos + 1){
            pos = min(n/(n/i), m/(m/i));
            res += (n/ i)* (m/i) * (summu[pos] - summu[i-1]);
        }
        return res;
    }
    
    int main(){
        getPrime();
        FOR(i,1,maxn){
            summu[i] = summu[i-1] + mu[i];
        }
        int T = readInt();
        while (T--){
            a = readInt();
            b = readInt();
            c = readInt();
            d = readInt();
            k = readInt();
            ll ans = solve(b / k , d / k) + solve((a-1)/k, (c-1)/k) - solve((a-1)/k, d/k) - solve(b/k, (c-1)/k);
            cout << ans << endl;
        }
    
        return 0;
    }
    

     

    展开全文
  • hdu1695 求1<=i<=n&&1<=j<=m,gcd(i,j)=k的(i,j)的对数 最后的结果f(k)=Σ(1<...=n/k)mu[x]*(n/(x*k))*(m/(x*k)) ...遍历的复杂度是O(n/k),按理来说是会t的,但是这过...这要(i,j)和(...

    hdu1695

    求1<=i<=n&&1<=j<=m,gcd(i,j)=k的(i,j)的对数

    最后的结果f(k)=Σ(1<=x<=n/k)mu[x]*(n/(x*k))*(m/(x*k))

    遍历的复杂度是O(n/k),按理来说是会t的,但是这题过了,更好的办法是用分块降低到O(sqrt(n/k))

    详细介绍请看:链接

    这题要(i,j)和(j,i)算重复的,所以要减去

    //#pragma comment(linker, "/stack:200000000")
    //#pragma GCC optimize("Ofast,no-stack-protector")
    //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    //#pragma GCC optimize("unroll-loops")
    #include<bits/stdc++.h>
    #define fi first
    #define se second
    #define mp make_pair
    #define pb push_back
    #define pi acos(-1.0)
    #define ll long long
    #define mod 1000000007
    #define C 0.5772156649
    #define ls l,m,rt<<1
    #define rs m+1,r,rt<<1|1
    #define pil pair<int,ll>
    #define pii pair<int,int>
    #define ull unsigned long long
    #define base 1000000000000000000
    #define fio ios::sync_with_stdio(false);cin.tie(0)
    
    using namespace std;
    
    const double g=10.0,eps=1e-12;
    const int N=100000+10,maxn=400000+10,inf=0x3f3f3f3f;
    
    int mu[N],prime[N],sum[N];
    bool mark[N];
    void init()
    {
        mu[1]=1;
        int cnt=0;
        for(int i=2;i<N;i++)
        {
            if(!mark[i])prime[++cnt]=i,mu[i]=-1;
            for(int j=1;j<=cnt;j++)
            {
                int t=i*prime[j];
                if(t>N)break;
                mark[t]=1;
                if(i%prime[j]==0){mu[t]=0;break;}
                else mu[t]=-mu[i];
            }
        }
        for(int i=1;i<N;i++)sum[i]=sum[i-1]+mu[i];
    }
    int main()
    {
        init();
        int t,cnt=0;
        scanf("%d",&t);
        while(t--)
        {
            ll a,b,c,d,k;
            scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
            if(!k)
            {
                printf("Case %d: 0\n",++cnt);
                continue;
            }
            if(b>d)swap(b,d);
            b/=k,d/=k;
            ll ans=0,ans1=0;
            for(ll i=1,last=1;i<=b;i=last+1)
            {
                last=min(b/(b/i),d/(d/i));
                ans+=(ll)(sum[last]-sum[i-1])*(b/i)*(d/i);
            }
            for(ll i=1,last=1;i<=b;i=last+1)
            {
                last=b/(b/i);
                ans1+=(ll)(sum[last]-sum[i-1])*(b/i)*(b/i);
            }
            printf("Case %d: %lld\n",++cnt,ans-ans1/2);
        }
        return 0;
    }
    /********************
    
    ********************/
    View Code

     

    转载于:https://www.cnblogs.com/acjiumeng/p/8439155.html

    展开全文
  • YY的gcd啊,,题意如下; 多组数据 每组数据给出n,m,k;...根据上文所说,莫比乌斯反演最重要的第一步是找准f 和F两个函数。 明显本f(d)指满足gcd(i,j)的对数。 那F的含义就如上文所示了。 所以 ...

    YY的gcd啊,,题意如下;

    多组数据

    每组数据给出n,m,k;

    求1<=i<=n,1<=j<=m,gcd(i,j)=k;的对数。

    数据数最高为10000,n,m<=10000000

    毒瘤数据。

    根据上文所说,莫比乌斯反演最重要的第一步是找准f 和F两个函数。

    明显本题f(d)指满足gcd(i,j)的对数。

    那F的含义就如上文所示了。

    所以

    f(d)=\sum_{i=1}^{n}\sum_{j=1}^m(gcd(i,j)=d)

    F(n)=\sum_{n|d}f(d)

    Ans=\sum_{p\in prim}\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)=p)

    把f(p)代入得

    Ans=\sum_{p\in prim}f(p)

    反演一下得

    Ans=\sum_{p\in prim}\sum_{p|d}\mu(\left \lfloor\frac{d}{p} \right \rfloor)F(d)

    可以看出这里我们在枚举质数,那我们换一下,枚举\left \lfloor \frac{d}{p} \right \rfloor,并将F代入后半截得

    Ans=\sum_{p\in prim}\sum_{d=1}^{min(\left \lfloor\frac{n}{p} \right \rfloor,\left \lfloor \frac{m}{p} \right \rfloor)}\mu(d)F(dp)=\sum_{p\in prim}\sum_{d=1}^{min(\left \lfloor \frac{n}{p}\right \rfloor,\left \lfloor \frac{m}{p} \right \rfloor)}\mu(d)\left \lfloor \frac{n}{dp}\right \rfloor\left \lfloor\frac{m}{dp} \right \rfloor

    为了方便表示,我们设T=dp

    Ans=\sum_{T=1}^{min(n,m)}\sum_{t|T,t\in prim}\mu(\left \lfloor \frac{T}{t} \right \rfloor)\left \lfloor \frac{n}{T} \right \rfloor\left \lfloor \frac{m}{T} \right \rfloor

    所以到现在为止,这个式子的复杂度已经是O(n)了。

    但是由于是多组数据,所以我们要把复杂度降成O(根号下n);观察式子发现很多向下取整得到的值是一样的(在T不一样的时候),所以我们运用整除分块。整除分块后一坨一坨处理就需要一个前缀和sum。

    整除分块很简单,,基本可以背代码,,大家请看代码就可以了。

    #include<bits/stdc++.h>
    #define in read()
    using namespace std;
    int in{
    	int cnt=0,f=1;char ch=0;
    	while(!isdigit(ch)){
    		ch=getchar();
    		if(ch=='-')f=-1;
    	}
    	while(isdigit(ch)){
    		cnt=cnt*10+ch-48;
    		ch=getchar(); 
    	}
    	return cnt*f;
    }
    int mul[10000003];
    int prim[10000003],vis[10000003],cnt;
    long long g[10000003],sum[10000003];//g与sum见mull处理区,自行理解ovo 
    int t;
    void mull(int n){
    	mul[1]=1;
    	for(int i=2;i<=n;i++){
    		if(!vis[i]){
    			prim[++cnt]=i;mul[i]=-1;
    		}
    		for(int j=1;j<=cnt&&prim[j]*i<=n;j++){
    			vis[prim[j]*i]=1;
    			if(i%prim[j]==0)break;
    			mul[prim[j]*i]=-mul[i];
    		}
    	}//筛完了mu 
    	for(int j=1;j<=cnt;j++){
    		for(int i=1;i*prim[j]<=n;i++){
    			g[prim[j]*i]+=mul[i];//g[i]存最终式子的最后面那一坨 
    		}
    	}
    	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+g[i];//g的前缀和 
    }
    int main(){
    	t=in;int n,m;
    	mull(10000000);
    	while(t--){
    		n=in;m=in;
    		if(n>m)swap(n,m);
    		long long ans=0;
    		for(register int l=1,r;l<=n;l=r+1){
    			r=min(n/(n/l),m/(m/l));//注意,这里是整除分块。经典的n/(n/l)保证分出来的复杂度最接近根号n 
    			ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);//前缀和的运用。 
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    } 

     

     

    展开全文
  • #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef long long ll; const int maxn=1e5+7; int prime[maxn],mu[maxn],tot;...ll sum[maxn]...
  • 题目链接: ... 题目大意: 求第k个无平方因子的数 思路: 二分答案x,求1-x中有多少个平方因子的数 可以在根号x的范围内求出来 1 #include<... 2 #define IOS ios::sync_with...
  • 莫比乌斯反演简单

    千次阅读 2015-08-10 21:11:24
    莫比乌斯函数这里简述一下莫比乌斯函数:...莫比乌斯反演的性质性质一:(莫比乌斯反演公式)f(n)=∑(d|n)μ(d)F(n/d)f(n) = \sum(d|n) {\mu(d)F(n/d)} 性质二:μ(n)是积性函数性质三:设f是算术函数,它的和函数F(n)=
  • 莫比乌斯反演模板

    2018-06-01 21:51:57
    莫比乌斯函数:莫比乌斯两种反演:d|n,表示n能够整除d,也就是d是n的所有因子μ(x)是莫比乌斯函数,它是这样计算的:(1).μ(1) = 1 (2).x = p1 * p2 * p3 ……*pk(x由k个不同的质数组成)则μ(x) = (-1)^k (3...
  • 莫比乌斯反演网络上的其他blog已经介绍得极其详尽了,因此虽然很有价值但是不作介绍。证明的话利用了欧拉函数的一些性质,不是很困难,信息安全数学基础也讲过,因此也不介绍。重要的还是题目和函数的构造。  贴...
  • 题目 //预处理后半部分 //f[i][j]:i的 所有k<=j的约数 的mu和.(其实不是他的mu之和 而是除以它得到的另一个因子的mu之和 推式子会有的啦) for(int d=1;d<=N;++d) for(int i=d;...i+=d) f[i][t[d]]+=mu[i/d];...
  • 可以通过反演简化时间复杂度至 ,将 代入,并且优先枚举T得: 交换枚举顺序 ,由 得 原式=   #include using namespace std; #define MAXN 100005 #define ll long long bool vis[MAXN]; ll prime[MAXN...
  • 来自Peterwuyihong 的单。 前置知识 前置芝士1 数论分块 UVA11526 H(n) P2261 [CQOI2007]余数求和 P2260 [清华集训2012]模积和 其中有一个式子需要注意一下:\[\sum_{i=1}^n\sum_{j=1}^m\left\lfloor\dfrac{n}{i}...
  • bzoj2301: [HAOI2011]Problem b:... 一看题目 模板题 模板题:caioj1280: [视频]【莫比乌斯反演模板题】GCD http://caioj.cn/problem.php?id=1280 证明:https://blog.csdn.net/herodeath...
  • 模板莫比乌斯反演

    2017-10-25 23:53:45
    如果有:  F(d)=∑i|df(i) 那么有:  f(d)=∑i|dμ(i)F(di)  另一种形式是如果  F(d)=∑d|if(i) 那么  f(d)=∑d|iμ(id)F(i) const int maxn=1e6+10;...void M
  • 的模数不一定是质数因此不能用费马小定理求逆元,考虑到n不是特别大可以直接除 Code #include #include typedef long long LL; const int N= 10000000 ; std :: map ,LL> map ...
  • 莫比乌斯反演 懵逼钨丝繁衍,你值得拥有 莫比乌斯反演是啥 若我们需要一个函数f(x)f(x)f(x),它非常的不好求 同时我们有一个函数F(x)F(x)F(x),它非常的好求 并且f(x)f(x)f(x)与F(x)F(x)F(x)之间的关系为: F...
  • 关于莫比乌斯反演的总整理,几乎目前遇到的所有ACM中涉及到莫比乌斯反演都可以用代码中的函数解决。
  • 莫比乌斯反演的形式: 另一种描述是: 一种是和所有的约数有关一种是和所有的倍数有关,解题的时候要根据题目选择合适的表达形式,感觉第二种用的比较多。 关于莫比乌斯函数mu,他的定义如下: 这个...
  • 一、莫比乌斯反演 我们先来看一个函数:\(F(x)=\sum_{d\mid x} f(d)\) 我们先枚举一下这个函数的各个值 \(F(1)=f(1)\) \(F(2)=f(1)+f(2)\) \(F(3)=f(1)+f(3)\) \(F(4)=f(1)+f(2)+f(4)\) \(F(5)=f(1)+f(5)\) \(F(6)=f...
  • 看了这个博客:莫比乌斯反演详解   构造是重点,现在看这:   构造方法和上面的讲解中的构造是基本一致的 #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;cmath&...
  • 莫比乌斯反演#include&lt;cstdio&gt; #include&lt;algorithm&gt; using namespace std; const int L = 66666; int mu[L],primes[L]; bool isPrime[L]; int n,num; void sieve(){ fill(isPrime,...
  • 莫比乌斯反演模版

    2016-07-06 10:40:00
    //--莫比乌斯反演函数--// //说明:利用线性素数筛选顺便求了个mu //注释部分为求从区间[1,b]和区间[1,d]中取两个数,互质对数O(n^0.5) //复杂度:O(n) int mu[N]; //int sum[N]; void mobus() { ...
  • 一、莫比乌斯反演 学习笔记,我是看这个博客入门的,讲的非常好,传送门,关键是给出了非常多的定理,好多是数论书上的权威概念。 我自己证明的照片在文末,有点乱 首先,莫比乌斯反演是什么? 第一种形式: F(n)=∑...
  • 莫比乌斯反演模板题。 #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=...
  • [模板]莫比乌斯反演

    2019-01-05 23:00:00
    莫比乌斯反演 已知数论函数$F(n)$且$F(n)=\sum_{d|n}f(d)$ 则有$f(n)=\sum\limits_{d|n}\mu(d)F(\frac{n}{d})$ 以及另一种形式(d是n的倍数): $F(n)=\sum\limits_{n|d}f(d)$ $f(n)=\sum\limits_{n|d}\mu...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 833
精华内容 333
关键字:

莫比乌斯反演模板题