【洛谷】提高历练地 - 数论

àì夳堔傛蜴生んèń 2023-06-30 08:38 2阅读 0赞

###  ###

*  P2152 \[SDOI2009\]SuperGCD（大数gcd）
 *  P1414 又是毕业季II（最大因子）
 *  P1134 阶乘问题（模运算）
 *  P1313 计算系数（杨辉三角 + 快速幂）

# P2152 \[SDOI2009\]SuperGCD（大数gcd） #

> **原题链接：**[https://www.luogu.com.cn/problem/P2152][https_www.luogu.com.cn_problem_P2152]

*  **思路：** 求两个高精度数的最大公约数，直接用 Java 的大数类即可，或者直接调用 Python 的一个库 fractions Fraction 类的 gcd ，也可以用 Python 的辗转相除法或者更相减损法。

**Code1（Java）：**

import java.util.*;
    import java.math.*;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner cin = new Scanner(System.in);
            BigInteger a = cin.nextBigInteger();
            BigInteger b = cin.nextBigInteger();
            System.out.println(a.gcd(b));
        }
    }

**Code2（Python）：**

import fractions
    print(fractions.gcd(int(input()),int(input())))

**Code3（Python）：**

//更相减损法
    def gcd(a,b):
        while(a!=b):
            if(a>b):
                a-=b
            else:
                b-=a
        return a
    print(gcd(int(input()),int(input())))

**Code4（Python）：**

//辗转相除法
    def gcd(a,b):
        while(a!=0):
            b%=a
            t=a
            a=b
            b=t
        return b
    print(gcd(int(input()),int(input())))

# P1414 又是毕业季II（最大因子） #

> **原题链接：**[hhttps://www.luogu.com.cn/problem/P1414][hhttps_www.luogu.com.cn_problem_P1414]

*  **思路：** 每个数的每个因子只能出现一次，所以先把每个数的因子求出来，将因子出现的次数存入数组，然后求 i 个数最大的因子其实就是求出现次数为 i 的最大因子。

**Code（C++）：**

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=0x3f3f3f3f;
    const int pi=acos(-1.0);
    const int mod=10007;
    int a[1001000];
    inline int read(){ 
        char c=getchar();    int num=0;
        for(;!isdigit(c);c=getchar());
        for(;isdigit(c);c=getchar())
            num=num*10+c-'0';
        return num;
    }
    ll q_pow(ll a, ll b, ll Mod){ 
        ll ans=1,base=a;
        while(b){ 
            if(b&1) ans=ans*base%Mod;
            base=base*base%Mod;
            b>>=1;
        }
        return ans;
    }
    ll gcd(ll a, ll b){ 
        return b==0?a:gcd(b,a%b);
    }
    int main(){ 
        int n=read(),maxn=0;
        for(int i=1;i<=n;i++){ 
            int x;  x=read();
            maxn=max(maxn,x);
            for(int j=1;j*j<=x;j++){ 
                if(x%j==0){ 
                    a[j]++;
                    if(x!=j*j)  a[x/j]++;
                }
            }
        }
        for(int i=1;i<=n;i++){ 
            while(a[maxn]<i)    maxn--;
            cout<<maxn<<endl;
        }
        return 0;
    }

# P1134 阶乘问题（模运算） #

> **原题链接：**[https://www.luogu.com.cn/problem/P1134][https_www.luogu.com.cn_problem_P1134]

*  **思路：**

1.  因为 2 \* 5 = 10，所以把相同数量的 2 和 5 因子删掉。可想而知，2 的数量比 5 多，所以只需要求出 2^(2的个数-5的个数)\*其他数%10 ，要注意的就是每一步操作都保留一位尾数即可。
2.  也可以直接暴力求，每一次的结果对 100000000 取模。

**Code1（C++）：**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #define ll long long
    using namespace std;
    const int maxn=0x3f3f3f3f;
    const int pi=acos(-1.0);
    inline int read(){ 
        char c=getchar();    int num=0;
        for(;!isdigit(c);c=getchar());
        for(;isdigit(c);c=getchar())
            num=num*10+c-'0';
        return num;
    }
    int m=0;
    int f(int x){ 
        int y=x;
        while(y%2==0){ 
            m++;
            y/=2;
        }
        while(y%5==0){ 
            m--;
            y/=5;
        }
        return y;
    }
    int main(){ 
        int n=read(),ans=1;
        for(int i=2;i<=n;i++)
            ans=(ans*f(i))%10;
        for(int i=1;i<=m;i++)
            ans=(ans*2)%10;
        cout<<ans<<endl;
        return 0;
    }

**Code2（C++）：**

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=0x3f3f3f3f;
    const int pi=acos(-1.0);
    inline int read(){ 
        char c=getchar();    int num=0;
        for(;!isdigit(c);c=getchar());
        for(;isdigit(c);c=getchar())
            num=num*10+c-'0';
        return num;
    }
    int main(){ 
        ll n=read(),ans=1;
        for(int i=1;i<=n;i++){ 
            ans*=i;
            while(ans%10==0)
                ans/=10;
            ans%=100000000;
        }
        cout<<ans%10<<endl;
        return 0;
    }

# P1313 计算系数（杨辉三角 + 快速幂） #

> **原题链接：**[https://www.luogu.com.cn/problem/P1313][https_www.luogu.com.cn_problem_P1313]

*  **思路：** 根据二项式定理，当 a = 1，b = 1时，每一项的系数构成了杨辉三角形，然后杨辉三角第k+1行、第k-n+1列就是答案。当 a，b 不一定等于 1 时，其结果就是 杨辉三角的值再乘 (a^n) 再乘 (b^m) 。

**Code（C++）：**

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=0x3f3f3f3f;
    const int pi=acos(-1.0);
    const int mod=10007;
    ll a,b,k,n,m,f[1010][1010];
    inline int read(){ 
        char c=getchar();    int num=0;
        for(;!isdigit(c);c=getchar());
        for(;isdigit(c);c=getchar())
            num=num*10+c-'0';
        return num;
    }
    void yanghui(){ 
        f[1][1]=1;
        for(int i=2;i<=k+1;i++)
            for(int j=1;j<=i;j++)
                f[i][j]=(f[i-1][j]%mod+f[i-1][j-1]%mod)%mod;
    }
    ll q_pow(ll a, ll b, ll Mod){ 
        ll ans=1,base=a;
        while(b){ 
            if(b&1) ans=ans*base%Mod;
            base=base*base%Mod;
            b>>=1;
        }
        return ans;
    }
    int main(){ 
        cin>>a>>b>>k>>n>>m;
        yanghui();
        cout<<(((f[k+1][k+1-n]%mod)*q_pow(a,n,mod))%mod)*q_pow(b,m,mod)%mod<<endl;
        return 0;
    }

[https_www.luogu.com.cn_problem_P2152]: https://www.luogu.com.cn/problem/P2152
[hhttps_www.luogu.com.cn_problem_P1414]: https://www.luogu.com.cn/problem/P1414
[https_www.luogu.com.cn_problem_P1134]: https://www.luogu.com.cn/problem/P1134
[https_www.luogu.com.cn_problem_P1313]: https://www.luogu.com.cn/problem/P1313