算法总结—最小公倍数+取模

LRRabcd · 2024-10-07 18:53:37 · 算法·理论

\text{GCD}

\text{GCD} 的几个公式：

\gcd(x,y)\times\text{lcm}(x,y)=xy
\gcd(x,y)=\gcd(y,x)
\gcd(a_1,a_2,...,a_n)\leq\min\{a_i\}
\gcd(x,y)=\gcd(y,x\bmod y)

由第四条公式我们可以得出求两数最大公约数的代码：

int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}

文文的数学游戏

第一问

根据 \gcd 的第三条公式，我们可知 \gcd(b_1,b_2,...,b_n) 最大只可能是 \min\{a_i\}，

第二问

由于每一个 b_i 都得是 \min\{a_i\} 的倍数，所以，每种 b_i 都有 a_i\div\min\{a_i\} 种可能的值，根据乘法原理，最终的答案就是 (a_1\div\min\{a_i\})\times(a_1\div\min\{a_i\})\times ...\times(a_n\div\min\{a_i\}) 。

记得取模，记得开 long long 。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
const int mod=1e9+7;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int cnt=1;
    int Min=1e18;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        Min=min(Min,a[i]);
    }
    for(int i=1;i<=n;i++){
        cnt*=a[i]/Min;
        cnt%=mod;
    }
    cout<<Min<<" "<<cnt;
    return 0;
}

\text{Change}

由于初始值为 0，所以我们可以把乘法看作一个加法 (x\times a)\bmod p\to(x+kx)\bmod p。又因为 p 为质数，所以他每一次模 p 是都会比上一次有一个偏移量，导致 0 至 p-1 的所有熟都被覆盖。所以这道题中只要 b=0 且 c\neq0 就输出 No ，其余情况输出 Yes 。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int T;
    cin>>T;
    while(T--){
        int p,a,b,c;
        cin>>p>>a>>b>>c;
        if(b==0&&c!=0){
            cout<<"No\n";
            continue;
        }
        cout<<"Yes\n";
    }
    return 0;
}

\text{Running}

这道题中的 V 要整除所有的 a_i 且 \frac{a_i}{V} 为偶数，我们设 \frac{a_i}{V}=2k ，则 \frac{a_i}{2V}=k ，这样我们就可以得出 V 就等于 \gcd(\frac{a_i}{2})。

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x%2==1){
            cout<<-1;
            return 0;
        }
        ans=gcd(ans,x/2);
    }
    cout<<ans;
    return 0;
}

取模

模法公式：

int add(int x,int y){//加 
    return ((x%mod)+(y%mod))%mod;
} 
int sub(int x,int y){//减 
    return ((x%mod)-(y%mod)+mod)%mod;
} 
int mul(int x,int y){//乘 
    return ((x%mod)*(y%mod))%mod;
}

\text{The\ Grand\ Farm-off\ S}

这道题有两个公式：

W_i=(a\times i^5+b\times i^2+c)\mod d

U_i=(e\times i^5+f\times i^3+g)\mod h

这道题要是硬算肯定会爆 long long ，于是我们根据模法公式一步步算出来：

算出 i^5。
算出 a\times i^5。
算出 i^2。
算出 b\times i^2。
将 a\times i^5,b\times i^2,c 加起来。计算 U_i 同理。

嘴里用结构体排序：

有用度相等按照体重从轻到重排，否则按照有用都从大到小排。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a,b,c,d,e,f,g,h;
int mod;
struct node{
    int w,val;
}pre[1500005];
bool cmp(node q,node h){
    if(q.val==h.val){
        return q.w<h.w;
    }
    return q.val>h.val;
}
int MUL(int a,int b){
    return ((a%d)*(b%d))%d;
}
int ADD(int a,int b){
    return ((a%d)+(b%d))%d;
}
int MUL_(int a,int b){
    return ((a%h)*(b%h))%h;
}
int ADD_(int a,int b){
    return ((a%h)+(b%h))%h;
}
int add(int a,int b){
    return ((a%mod)+(b%mod))%mod;
}
signed main(){
    cin>>n;
    cin>>a>>b>>c>>d>>e>>f>>g>>h;
    cin>>mod;
    int N=n*3;
    for(int i=0;i<N;i++){
        int I=MUL(i,i);
        I=MUL(I,i);
        I=MUL(I,i);
        I=MUL(I,i);
        int A=MUL(a,I);
        I=MUL(i,i);
        int B=MUL(b,I);
        int C=c;
        pre[i].w=ADD(ADD(A,B),C);
    }
    for(int i=0;i<N;i++){
        int I=MUL_(i,i);
        I=MUL_(I,i);
        I=MUL_(I,i);
        I=MUL_(I,i);
        int E=MUL_(e,I);
        I=MUL_(i,i);
        I=MUL_(I,i);
        int F=MUL_(f,I);
        int G=g;
        pre[i].val=ADD_(ADD_(E,F),G);
    }
    sort(pre,pre+N,cmp);
    int cnt=0;
    for(int i=0;i<n;i++){
        cnt=add(cnt,pre[i].w);
    }
    cout<<cnt;
    return 0;
}