本次训练共10题,本文附AC代码和题目链接。

关于gcd的时间复杂度

gcd的复杂度最坏也不超过log2(n)

在《离散数学》上给出了一个证明(P77),可以证明,gcd的运行次数不会超过2*log2(n+1),n为较小数。

在上述证明的旁边,还给出了一个结论,拉梅定理:gcd的运行次数,不会超过较小数十进制位数的5倍,也就是5*log10(n)

(参考文章:https://blog.csdn.net/fengyuzhicheng/article/details/79561300

gcd非递归模板

typedef long long ll;
ll gcd(ll a,ll b)
{
    ll r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

gcd递归模板

long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}

nefu 1411 LCM&GCD

假设gcd(a,b)=x,lcm(a,b)=y,则可得:gcd*lcm=a*b,即x*y=a*b
在[x,y]区间内暴力遍历所有a的取值,可以直接得到b的值b=x*y/a
若b在[x,y]范围内,并且gcd(a,b)==x,即满足条件,答案+1。
(事实上b一定在[x,y]范围内,因为a∈[x,y],又有b=x*y/a,则b∈[x,y])

这是时间复杂度O(t*n)的解法,时间1s的话肯定不能过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;}
ll t,x,y,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>x>>y;//假设gcd(a,b)=x,lcm(a,b)=y,则可得:gcd*lcm=a*b,即x*y=a*b
        ans=0;
        for(ll a=x;a<=y;a+=x)//在[x,y]区间内暴力遍历所有a的取值,a每次+x(比每次+1要快)
        //每次+x的原因是,由于x是a和b的最大公约数,则a一定是x的倍数,所以只需+x即可
        {
            if((x*y)%a==0)//满足a*b=x*y,则b=x*y/a,首先必须满足(x*y)%a==0
            {
                ll b=x*y/a;//直接得到b的取值
                if(gcd(a,b)==x)ans++;//gcd(a,b)==x,即满足条件
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

改进算法,O(t*sqrt(n))的解法:

假设gcd(a,b)=x,lcm(a,b)=y,则可得:gcd*lcm=a*b
即x*y=a*b,同除以x^2^,得y/x=(a/x)*(b/x)
令y1=y\/x,a1=a/x,b1=b/x
则y1=a1*b1,且a1∈[1,y1]

这样化简之后,再遍历[1,sqrt(y1)](只需遍历到 根号y1 即可)找满足gcd(a1,b1)==1的情况,更新答案。

注意特判a1*a1=y的情况,答案+1;其他情况答案+2。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b,x,y,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>x>>y;
        ans=0;
        if(y%x!=0){printf("0\n");continue;}//最小公倍数不是最大公约数的倍数,直接输出0
        y=y/x;//将y缩小到y1
        for(a=1;a*a<=y;a++)//在[1,y1]区间内暴力遍历所有a1的取值,a每次+1
        {
            if(y%a==0)//满足y1=a1*b1,则b1=y1/a1,首先必须满足y1%a1==0
            {
                b=y/a;//直接得到b1的取值
                if(__gcd(a,b)==1)//gcd(a1,b1)==1则满足条件
                {
                    if(a*a==y)ans++;//特判a1*a1=y的情况,答案+1
                    else ans+=2;//其他情况答案+2
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

nefu 1077 最大公约数和最小公倍数 (模板题)

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}
long long lcm(long long a,long long b)
{return a/gcd(a,b)*b;}
int main()
{
    long long a,b;
    while(cin>>a>>b)
    {printf("%lld %lld\n",gcd(a,b),lcm(a,b));}
    return 0;
}

其实强大的C++内置了gcd函数!使用方法:__gcd(a,b)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b;
    while(cin>>a>>b)
        printf("%lld %lld\n",__gcd(a,b),a/__gcd(a,b)*b);
    return 0;
}

nefu 992 又见GCD

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
    int a,b,i;
    while(cin>>a>>b)
    {
        for(i=b+1;;i++)
        {
            if(gcd(a,i)==b)
            {printf("%d\n",i);break;}
        }
    }
    return 0;
}

nefu 764 多个数的最大公约数

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}
int main()
{
    long long n,i,a[11];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            cin>>a[i];
        for(i=1;i<=n-1;i++)
            a[i+1]=gcd(a[i],a[i+1]);
        printf("%lld\n",a[n]);
    }
    return 0;
}

nefu 765 多个数的最小公倍数

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;}
long long lcm(long long a,long long b)
{return a/gcd(a,b)*b;}
int main()
{
    long long n,i,a[11];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            cin>>a[i];
        for(i=1;i<=n-1;i++)
            a[i+1]=lcm(a[i],a[i+1]);
        printf("%lld\n",a[n]);
    }
    return 0;
}

nefu 1221 人见人爱gcd

这题要用数学公式推导出gcd(x,y)=gcd(a,b)
从而得到 x² + y² = a²-2 * b * gcd(a,b)

推导过程如下:
在这里插入图片描述
AC代码:

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
    int t,a,b;
    ios::sync_with_stdio(false);
    while(cin>>t)
    {
        while(t--)
        {
            cin>>a>>b;
            printf("%d\n",a*a-2*b*gcd(a,b));
        }
    }
    return 0;
}

nefu 1669 高木同学的因子

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y,i,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>x>>y;
    ll k=__gcd(x,y);
    for(i=1;i*i<k;i++)
        if(k%i==0)ans+=2;
    if(i*i==k)ans++;
    printf("%lld\n",ans);
    return 0;
}

nefu 601 快速幂取模 (模板题)

#include <bits/stdc++.h>
using namespace std;
long long mode(long long a,long long b,long long mod)
{
    long long ans=1;
    while(b)
    {
        if(b%2==1)
        {b--;ans=ans*a%mod;}
        a=a*a%mod;
        b=b/2;
    }
    return ans;
}
int main()
{
    long long a,b,c;
    while(cin>>a>>b>>c)
    printf("%lld\n",mode(a,b,c));
    return 0;
}

nefu 1666 库特的数学题

打表找规律,可以发现 a[n]=6*3^(n-1)^,用快速幂求解即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,mod=1e9+7;
ll quickmod(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1)s=s*a%mod;
        a=a*a%mod;b=b/2;
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    printf("%lld\n",6*quickmod(3,n-1)%mod);//注意算出3的n-1次幂,再乘以6之后一定还要再取模!
    return 0;
}

nefu 1834 异或方程解的个数

移项n=(n⊕x)+x(⊕表示异或)

可以发现若n的某个二进制位为1,x有2种取值;若n的某个二进制位为0,x有1种取值。

所以只需要计算出n的二进制中1的个数,假设为num,答案就是2^num^。

(不用快速幂也行,每次找到n中二进制位为1的地方就直接乘2即可)

AC代码:

#include <bits/stdc++.h>
using namespace std;
int qpow(int a,int b)
{
    int s=1;
    while(b)
    {
        if(b&1)s=s*a;
        b=b/2;
        a=a*a;
    }
    return s;
}
int main()
{
    int x,num;
    ios::sync_with_stdio(false);
    while(cin>>x)
    {
        num=0;
        while(x)
        {
            if(x&1)num++;
            x=x/2;
        }
        printf("%d\n",qpow(2,num));
    }
    return 0;
}