基础数论训练1

爱被打了一巴掌 2021-09-16 01:42 439阅读 0赞

\*可以通过旁边的目录查看(´・ω・\`)，或者Ctrl + F

# Least Common Multiple （HDU - 1019） #

## 难度：0/5，1A ##

## 解法：LCM ##

## 代码： ##

# 最小公倍数 HDU - 1108 #

## 难度：0/5，1A ##

## 解法：LCM ##

## 代码： ##

# RSA HDU - 1211 #

## 难度：1/5，1A ##

## 题意：解码 ##

## 解法：仔细读题后会发现，就是要求出d，然后快速幂.d∗e≡1(modFn)  d ∗ e ≡ 1 ( mod F n )  ,求d就是求一波e的逆元，解决 ##

## 代码 ##

# Wolf and Rabbit HDU - 1222 #

## 难度：1/5 ，1A ##

## 题意：0到n-1组成一个圆，从0开始，每次跳m步，看能否跳完所有的格子 ##

## 解法：本质就是求gcd(n,m)  g c d ( n , m ) ，假如gcd(n,m)  g c d ( n , m )  = 1，则能跳完 ##

## 代码： ##

# Biorhythms HDU - 1370 #

## 难度：1/5，1A ##

## 题意：人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。 ##

## 解法：23，28，33互质，裸的中国剩余定理 ##

## 代码： ##

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    
    ll exgcd(ll a,ll b,ll& d,ll& x,ll& y)
    {
        if(!b) { d=a; x=1; y=0; }
        else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
    }
    ll inv(ll a,ll n)
    {
        ll d,x,y;
        exgcd(a,n,d,x,y);
        return d==1? (x+n)%n:-1;
    }
    const int N = 10;
    ll a[N],m[N];
    ll china(int n)
    {
        ll M=1,d,x=0,y;
        for(int i=1;i<=n;i++) M*=m[i];
        for(int i=1;i<=n;i++)
        {
            ll w=M/m[i];
            exgcd(m[i],w,d,d,y);
            x=(x+y*w*a[i])%M;
        }
        return (x+M)%M;
    }
    
    int p,e,i,d;
    
    int main(int argc, char const *argv[])
    {
        int cas = 1;
        cin>>p;
        while(scanf("%d%d%d%d",&p,&e,&i,&d)!=EOF)
        {
            if(p ==-1 && e == -1 &&  i == -1 && d == -1)
                break;
            printf("Case %d: the next triple peak occurs in ",cas++);
            ll MOD = 23 * 28 * 33;
            m[1] = 23,m[2] = 28,m[3] = 33;
            a[1] = p,a[2] = e,a[3] = i;
            ll ans = ((china(3)-d)%MOD+MOD)%MOD;
            if(ans)
            cout<<ans;
            else
            cout<<MOD;
            printf(" days.\n");
        }   
        return 0;
    }

# Prepared for New Acmer HDU - 1420 #

## 难度：2/5，1A ##

## 题意：求A^B mod C ##

## 解法：A和B不保证互质，ab%p=(a%p)φ(p)\+b%φ(p)%p  a b % p = ( a % p ) φ ( p ) + b % φ ( p ) % p  ##

## 代码： ##

# Remainders Game CodeForces - 688D\\ #

## 难度：2/5，3A(t2) ##

## 题意：给你k和n，你现在想要知道x，给你n个ci  c i ，表示你可以知道x%ci  x % c i 问你能不能唯一确定x ##

## 解法：可以很快就想到中国剩余定理，如果我们想知道x%m等于多少，当且仅当我们知道x%m1  x % m 1 ,x%m2  x % m 2 …,x%mr  x % m r 分别等于多少，其中m1m2...mr=m  m 1 m 2 . . . m r = m ，并且mi  m i 相互互质.令m的分解为m=pk11pk22...pkrr  m = p 1 k 1 p 2 k 2 . . . p r k r ，如果任意i，都有pkii  p i k i 的倍数出现在集合中，那么m就能被猜出来。这个问题等价于问LCM(ci  c i )%m是否等于0,所以只要求出LCM(ci  c i )即可。 ##

## 代码： ##

# Chinese remainder theorem again HDU - 1788 #

## 难度：1/5，2A(wa1) ##

## 题意：与CRT没什么关系 ##

## 解法：一般题目说什么again，都跟前面的没什么关系，都是套路~，N≡m−a(modm)  N ≡ m − a ( mod m )  等价于N\+a≡0(modm)  N + a ≡ 0 ( mod m )  ，然后就是求lcm(mi)  l c m ( m i ) ，结果减a就是答案 ##

## 代码： ##

# X问题 HDU - 1573 #

## 难度：2/5，3A(1wa,1re) ##

## 题意: CRT，但是mi  m i 不保证互质 ##

## 解法：不互质怎么搞呀，不会了呀，(っ °Д °)っ，更新一波模板，你看，全TM是套路╰(∗°▽°∗)╯  ╰ ( ∗ ° ▽ ° ∗ ) ╯  ##

## 代码： ##

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    
    
    ll exgcd(ll a,ll b,ll& d,ll& x,ll& y)
    {
        if(!b) { d=a; x=1; y=0; }
        else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
    }
    //逆元
    //a*inv(a,n) = 1 mod n
    const int N = 15;
    ll inv(ll a,ll n)
    {
        ll d,x,y;
        exgcd(a,n,d,x,y);
        return d==1? (x+n)%n:-1;
    }
    ll A[N],b[N],m[N];
    typedef pair<ll, ll> PLL;
    PLL linear(ll A[], ll B[], ll M[], int n) {
       //求解A[i]x = B[i] (mod M[i]),总共n个线性方程组 
        ll x = 0, m = 1;
        for(int i = 0; i < n; i ++) {
            ll a = A[i] * m, b = B[i] - A[i]*x, d = gcd(M[i], a);
            if(b % d != 0)  return PLL(0, -1);//答案不存在，返回-1 
            ll t = b/d * inv(a/d, M[i]/d)%(M[i]/d);
            x = x + m*t;
            m *= M[i]/d;
        }
        x = (x % m + m ) % m;
        return PLL(x, m);//返回的x就是答案，m是最后的lcm值 
    }
    int n,t;
    int main(int argc, char const *argv[])
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            ll MOD = 1;
            memset(A,1,sizeof A);
            memset(m,0,sizeof m);
            memset(b,0,sizeof b);
            scanf("%d%d",&n,&t);
            rep(i,0,t)
            {
                A[i] = 1;
                scanf("%lld",&m[i]);
                //MOD *= m[i];//debug
            }
            rep(i,0,t)
            {
                scanf("%lld",&b[i]);
            }
            //cout<<MOD<<endl;
            PLL ans = linear(A,b,m,t);
            //cout<<ans.first<<endl;
            if(ans.first > n || ans.second == -1)
                cout<<0<<endl;
            else if(ans.first)
                cout<<(n - ans.first)/ans.second + 1<<endl;
            else
                cout<<n/ans.second<<endl;
            //ll sum = (n - ans.first)/MOD + 1;//debug
            //cout<<sum<<endl;
        }
        return 0;
    }

# YAPTCHA HDU - 2973 #

## 难度：2/5，1A(看了题解） ##

## 题意：求和 ##

## 解法：不会呀，这好熟悉但是不会呀，威尔逊定理：当且仅当p为素数时：(p−1)!≡−1(mod p)  ( p − 1 ) ! ≡ − 1 ( m o d   p ) .或者这么写(p−1)!≡p−1(mod p)  ( p − 1 ) ! ≡ p − 1 ( m o d   p ) ,或者说若p为质数，则p能被(p-1)!+1整除。在初等数论中,这是威尔逊给出了判定一个自然数是否为 素数 的 充分必要条件\\但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。(´・ω・\`)这不是就用上了吗。。。 ##

## 代码： ##