Java教程

蓝桥杯 第八讲 数论

本文主要是介绍蓝桥杯 第八讲 数论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、算法

1.欧几里得算法(辗转相除法求最大公约数)

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}

辗转相减法（求最大公约数）

即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。例如 ：两个自然数35和14，用大数减去小数，(35,14)->(21,14)->(7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，再做一次相减，结果为0，这样也就求出了最大公约数7

LL gcd_sub(LL a,LL b)//辗转相减法求最大公约数
{
    if(a<b) swap(a,b);
    if(b == 1) return a;
    return gcd_sub(b,a/b);
}

2.算术基本定理

image

3.筛法求素数——线形筛法

求1——n中所有质数以及每个数的最小质因子
image

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if(!st[i])
        {
            primes[cnt++] = i;
        }
        for(int j = 0;primes[j]<=n/i;j++)
        {
            int t = primes[j] * i;
            st[t] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

4.约数之和、约数个数

image

5.扩展欧几里得算法(裴蜀定理)

对于任意正整数a,b,若a和b的最大公约数为d，那么一定存在一组整数x,y，使得ax+by = d
image

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y-= a/b * x;
    return d;
}

二、例题

1246. 等差数列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N],n;
int ans;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    sort(a,a+n);
    int Min = 0x3f3f3f3f;
    for (int i = 1; i < n - 1; i ++ )
    {
        Min = min(gcd(a[i] - a[i-1],a[i+1] - a[i]),Min);
    }
    if(Min == 0)
    {
        cout << n << endl;
        return 0;
    }
    ans = (a[n-1] - a[0])/Min + 1;
    cout << ans << endl;
    return 0;
}

1295. X的因子链

image
image

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = (1<<20) + 10;
int x;
int primes[N],cnt;
int minp[N];  //最小质因子
bool st[N];  //是否被筛除

void get_primes(int n)  //线形筛素数
{
    for(int i = 2;i<=n;i++)
    {
        if(!st[i]) 
        {
            primes[cnt++] = i;
            minp[i] = i;  // 起初，最小质因子是其本身
        }
        for(int j = 0;primes[j]*i<=n;j++)
        {
            int t = primes[j]*i;
            st[t] = true;  //标记合数
            minp[t] = primes[j];
            if(i % primes[j] == 0) break;//如果i是前面某个素数的倍数时，之后的筛数是没有必要的，跳出循环
        }
    }
}
int main()
{
    get_primes(N - 1);
    int fact[30],sum[N]; //分别表示质因数及其次幂
    while(scanf("%d",&x)!=EOF)
    {
        int k = 0,tot = 0;//tot用于记录最大长度，k表示第i个因子的下标
        while(x>1) //依次处理各个质因子，求出对应质因子出现的次数
        {
            int p = minp[x]; //依次取出最小质因子
            fact[k] = p,sum[k] = 0;
            while(x%p==0)
            {
                x/=p;
                sum[k]++;
                tot++;
            }
            k++;
        }
        LL res = 1;
        for(int i = 1;i<=tot;i++) res*=i; //求所有质因子出现总次数的全排列
        for(int i=0;i<k;i++) //去除各个质因子重复出现的次数
        {
            for(int j = 1;j<=sum[i];j++)
            {
                res/=j;
            }
        }
        printf("%d %lld\n",tot,res);//输出最长序列的长度, 以及满足最大长度的序列的个数
    }
    return 0;
}

1296. 聪明的燕姿

image

1299. 五指山

这题的题意是让我们求x+bd = y+an ,整理得：-an+bd = y-x
但是我们得扩展欧几里得定理只能求 -an+bd = gcd(n,d)中的a和b，但是很容易看出y-x应该为gcd(n,d)的整数倍
否则无解。
因此我们只需要判断y-x是否为gcd(n,d)的整数倍就能判断是否有解了。
若有解我们利用扩展欧几里得定理就可以求得-an+bd = gcd(n,d)中的a和b，然后将a和b扩大 (y-x)/gcd(n,d)倍
就可以得到一组a0和b0，因为之前我们证过了获得一组解后其他解就可以表示出来了，我们只需要求一下所有解中的最小值就可以了（注意我们的b只能是正数，你总不能让大圣反着翻吧）
即：
求一下b = b0+k*(n/gcd(n,d))的最小值即可
minb = b0%(n/gcd(n,d));

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e9 + 10;

int T;
LL n,d,x,y,a,b;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return a;
    }
    LL d = exgcd(b,a%b,y,x);
    y -= a/b * x;
    return d;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld", &n, &d,&x,&y);
         
        LL mul = exgcd(n,d,a,b);
        if((y-x)%mul!=0)
        {
            puts("Impossible");
        }
        else
        {
            b *= (y-x)/mul;
            n/=mul;
            printf("%lld\n",(b%n+n)%n);
        }
    }
    return 0;
}

1223. 最大比例

image

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
typedef long long LL;
int n;
LL x[N];
LL a[N],b[N]; //表示每个比率的分母与分子
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL gcd_sub(LL a,LL b)//辗转相减法求最大公约数
{
    if(a<b) swap(a,b);
    if(b == 1) return a;
    return gcd_sub(b,a/b);
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%lld", &x[i]);
    }
    sort(x,x+n);
    int cnt = 0;
    for (int i = 1; i < n; i ++ ) //求出所有比例的最简分数形式
    {
        if(x[i-1]!=x[i]) //去重
        {
            LL mul = gcd(x[i],x[0]);
            b[cnt] = x[i]/mul;
            a[cnt] = x[0]/mul;
            ++cnt;
        }
    }
    LL fm = a[0],fz = b[0];
    for(int i = 1;i<cnt;i++)  //分开求分子分母的指数最大公约数
    {
        fm = gcd_sub(fm,a[i]);
        fz = gcd_sub(fz,b[i]);
    }
    cout << fz << '/'<< fm << endl;
    return 0;
}

1301. C 循环
image

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 32;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return a;
    }
    LL d = exgcd(b,a%b,y,x);
    y -= a/b * x;
    return d;
}

int main()
{
    LL a,b,c,k;
    
    while(cin>>a>>b>>c>>k,a||b||c||k)
    {
        LL x,y;
        LL z = (LL)1<<k; //2^k
        LL d = exgcd(c,z,x,y);
        if((b-a)%d!=0)
        {
            puts("FOREVER");
        }
        else
        {
            x = x * (b-a)/d;  //等式转换
            z = z / d;  //等式转换
            cout << (x % z + z) % z <<endl; //针对取模运算产生的负数问题处理
        }
    }
    return 0;
}

1225. 正则问题

image

#include <iostream>
#include <cstring>
#include <algorithm>
#include<string>
using namespace std;

const int N = 10005;

string str;
int k,len;
int dfs()
{
    int res = 0;
    while(k < len)
    {
        if(str[k] == '(')  //处理(......)
        {
            ++k;  //跳过左括号
            res += dfs();
            ++k;  //跳过右括号
        }
        else if(str[k] == '|')
        {
            ++k;  //跳过'|'
            res = max(res,dfs());
        }
        else if(str[k] == ')') break;
        else  //统计'x'
        {
            while(str[k] == 'x')
            {
                ++k;
                ++res;
            }
        }
    }
    return res;
}

int main()
{
    cin>>str; 
    len = str.size();
    int ans = dfs();
    cout << ans << endl;
    return 0;
}

1243. 糖果
image
image

这篇关于蓝桥杯 第八讲 数论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航