精华内容
下载资源
问答
  • 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

    展开全文
  • #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]...
    #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;
    bool p[maxn];
    ll sum[maxn];
    int T,a,b,c,d,k;
    
    void get_mu(){
        mu[1]=1;
        for(int i=2;i<maxn;i++){
            if(!p[i])prime[++tot]=i,mu[i]=-1;
            for(int j=1;i*prime[j]<maxn;j++){
                p[i*prime[j]]=1;
                if(i%prime[j]==0)break;
                mu[i*prime[j]]=-mu[i];
            }
        }
        for(int i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i];
    }
    int main()
    {
        get_mu();
        scanf("%d",&T);
        for(int t=1;t<=T;t++){
            scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
            printf("Case %d: ",t);
            if(k==0){printf("0\n");continue;}
            ll ans1=0,ans2=0;
            if(b>d)swap(b,d);b/=k,d/=k;
            for(int i=1,gi;i<=b;i=gi+1){
                gi=min(b/(b/i),d/(d/i));
                ans1+=(sum[gi]-sum[i-1])*(b/i)*(d/i);
            }
            for(int i=1,gi;i<=b;i=gi+1){
                gi=b/(b/i);
                ans2+=(sum[gi]-sum[i-1])*(b/i)*(b/i);
            }
            printf("%lld\n",ans1-ans2/2);
        }
        return 0;
    }
    
    展开全文
  • 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;
    } 

     

     

    展开全文
  • 而首当其冲的便是这啥莫比乌斯反演。话说第一次见到这名字还是莫比乌斯环。不知有没有人还有印象。好了,废话一大堆,切入正题。 【前言】 各位同学,如果你们想学这个貌似高深的算法,请先学习完caioj1157 线性...

    题目传送门
    那么在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 #...
  • 题目链接: ... 题目大意: 求第k个无平方因子的数 思路: 二分答案x,求1-x中有多少个平方因子的数 可以在根号x的范围内求出来 1 #include<... 2 #define IOS ios::sync_with...
  • 莫比乌斯反演模板

    2018-07-21 10:41:57
    莫比乌斯所需要的代码: #include"bits/stdc++.h" #define C(n,m) ((long long)fac[(n)]*inv[(m)]%MOD*inv[(n)-(m)]%MOD) using namespace std; const int maxn=3e5+5; const int MOD=1e9+7; ...
  • 看了这个博客:莫比乌斯反演详解   构造是重点,现在看这:   构造方法和上面的讲解中的构造是基本一致的 #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;cmath&...
  • 莫比乌斯反演模板题 看到互质什么的个数,,就想到莫比乌斯反演了吧,, 我们将f(n)设为下标gcd刚刚为n的组数,F(n)为下标的gcd为n的倍数的组数。。根据反演公式: #include #include #include #include ...
  • 思路:莫比乌斯反演模板题。 求对于区间[a,b]内的整数x和[c,d]内的y,满足gcd(x,y)=1的数对的个数。 只要让F(t)=满足gcd(x,y)%t==0的数对个数 f(t)=满足gcd(x,y)=t的数对个数,则F(t)和f(t)就存在莫比乌斯...
  • 莫比乌斯反演的公式

    千次阅读 2018-08-04 22:40:16
    一道经典的莫比乌斯反演题: 求:∑ni=1∑mj=1[gcd(i,j)==d]∑i=1n∑j=1m[gcd(i,j)==d] 也就是说有多少对(i,j)的gcd为d。  莫比乌斯反演公式  莫比乌斯函数 程序模板 void mobius() { int i,j; mbs...
  • bzoj2301: [HAOI2011]Problem b:... 一看题目 模板题 模板题:caioj1280: [视频]【莫比乌斯反演模板题】GCD http://caioj.cn/problem.php?id=1280 证明:https://blog.csdn.net/herodeath...
  • 题解:莫比乌斯反演是这样的 整除分块 要求的值时,通过打表可以发现会有很多相同的块: 1 2 3 4 5 6 7 8 9 10 10 5 3 2 2 1 1 1 1 1 for(ll l=1,r;l<=min(a,b);l=r+1){ r=n/(n/l) ans+=(r-l+...
  • 很久没做过莫比乌斯反演了,发现自己忘记莫比乌斯函数的线性筛法了,贴个模板方便复习吧 有一个埃氏筛做法,为了避免弄混,就只记一个好了 #include<bits/stdc++.h> using namespace std; #define go(i,a...
  • 最后是看https://blog.csdn.net/litble/article/details/72804050才懂...https://blog.csdn.net/litble/article/details/79509373根据我们做莫比乌斯反演题的经验,枚举gcd的值? https://blog.csdn.net/Control...
  • 莫比乌斯反演入门习题两道、莫比乌斯函数模板
  • 莫比乌斯反演】GCD1

    2017-09-22 19:46:03
    这题是莫比乌斯反演模板题 只要让F(t)=满足gcd(x,y)%t==0的数对个数 f(t)满足gcd(x,y)=t的数对个数,则F(t)和f(t)就存在莫比乌斯反演的关系了。显然F(t)=(b/t)*(d/t) 因为如果gcd(x,y)=1,则gcd(x?k,y?k)=k,所以...
  • bzoj 2301 莫比乌斯反演

    2017-09-12 21:31:00
    求$(i,j)=k$的一系列模板题之一。 但是这里i,j是有下界的,注意用容斥去掉重复组,其他都一样了。 /** @Date : 2017-09-09 19:21:18 * @FileName: bzoj 2301 莫比乌斯反演 多组 范围内 GCD=k.cpp * @...
  • 这是一道练习莫比乌斯反演模板题,下面先给出莫比乌斯反演的做法,最后再一种欧拉函数计算的思路 对于这种二元组的题,我们设分别为为倍数与正好为的个数(范围内) 即:,两者关系有,对其进行莫比乌斯反演 ,则原题的 ...
  • 题目描述:戳这里 题意:求∑1b∑1dGCD(x,y)=k∑1b∑1dGCD(x,y)=k\displaystyle\sum_1^b\sum_1^dGCD...但是,因为是莫比乌斯反演模板题,我们还是思考一下反演的做法吧。 作为一个初学者,表示一脸懵逼[钨丝反演...
  • μ(i)可通过莫比乌斯反演模板所求,需要注意若输入的k不等于1,即gcd(i,j) = k,等同于gcd(i/k,j/k) = 1。接下来问题就变得简单了,只需要注意(1,2)和(2,1)是等价的,所以需要排除。则如图 先定义一个ans算全部的对数...
  • Visible Lattice Points 题意 : 从(0,0,0)出发在(N,N,N)范围内有多少条不从重合的直线;我们只要求gcd(x,y,z) = 1;...莫比乌斯反演模板题, 由于点坐标可以为0 , 需要考虑 x, y, z 中两个为0 和一...
  • 首先是模板题三连 hdu1695——求gcd(x,y)=k的对数(注意去重) bzoj2301——求gcd(x,y)=k的对数(不用去重,在上题的基础上加了一个容斥,并且用整除分块加速求和) bzoj2818——求gcd(x,y)=p的对数(p是质数,...
  • 莫比乌斯模板题 ∑xi=1∑yj=1[gcd(i,j)==d]∑i=1x∑j=1y[gcd(i,j)==d]\sum_{i=1}^{x} \sum_{j=1}^{y} [gcd(i,j)==d] =∑⌊xd⌋i=1∑⌊yd⌋j=1[gcd(i,j)==1]=∑i=1⌊xd⌋∑j=1⌊yd⌋[gcd(i,j)==1]=\sum_{i=1}^{\...
  • 3.超水的模板题 1.莫(meng)比乌斯函数 怕你不知道,其实莫比乌斯函数是这个样子的 μ(n)=δw(n)Ω(n)λ(n); 但实际上这和今天所讲内容并没有什么直接联系 对于高中阶段的信息学而言,更需要的是“能够利用某种事物...
  • 这个就当做是模板吧。然后把两种形式贴出来: 第一种: 第二种: 然后是容斥的函数: 然后有一些性质: 再耍两道巩固一下。 #include <cstdio> #include <cstring> #include &....
  • 反演模板题 #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;queue&g...
  • 思路:莫比乌斯模板题。 #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;bitset&gt; #include &lt;cmath&gt; #include.....
  • 不过模板书给的代码是莫比乌斯反演。 赛后百度了一下题解,发现也可以用容斥做,思路和我赛场上的思路一样,但由于赛场上写容斥的时候想到dfs,感觉复杂度太高,而且剩下时间不多了,就自动开启了自闭模式。 下面...
  • 这道阔以作为模板莫比乌斯模板 并且代码里的函数的意义也与标准的相同: f(d,n,m)f(d,n,m)f(d,n,m) 代表小于等于 n、mn、mn、m 的 gcd(x,y)=dgcd(x,y)=dgcd(x,y)=d 的个数 F(d,n,m)F(d,n,m)F(d,n,m) 代...

空空如也

空空如也

1 2 3 4
收藏数 64
精华内容 25
关键字:

莫比乌斯反演模板题