数论之gcd的应用

H. 找朋友 [ Problem 4047 ] [ Discussion ]

Description

中秋节快到了，rrz想去找她的好朋友。

rrz所在的地图是一个二维坐标系，她所在的位置是

rrz受限于交通工具的影响，假设他当前位置是

问你rrz是否能成功找到她的好朋友。

Input

第一行一个数t；

然后t行，每行四个数，代表rrz的位置和rrz的好朋友的位置。

Output

Samples

Input Copy

1
1 2 1 3

Output

1
就是有一种求gcd的方法，就是这么求得

更相减损法

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template <typename Tp>
void read(Tp &x){//read(n);
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
inline char read1()//字符串读入挂
{
    register char ch=getchar();
    while(ch<'A'||ch>'M')ch=getchar();
    return ch; 
}
const int maxn=5e5+100;
ll gcd(ll a,ll b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        if(gcd(a,b)==gcd(c,d)){
            printf("1
");
        } 
        else{
            printf("0
"); 
        }
    } 
}

例二：

传送门

有一座山旁边为N个山洞，编号为0,1,2,3,4,...n-1
一头兔子和一只狼来到了这座山上.为了防止被狼捉到，兔子需要藏进某个洞里，狼第一次进入编号为0的洞口，然后每次只能前进m个洞口，例如m=2，n=6，则狼将进入0,2,4,0,2,4....所以兔子只需躲在编号为1 3 5 的洞里即可逃生

Input第一行一个正整数P，代表测试样例数目. 接下来P行每行包含两个正整数m and n(0<m,n<2147483648).
Output对于每组数据, 如果兔子能够成功逃生，输出 "YES", 否则输出 "NO"
Sample Input

2
1 2
2 2

Sample Output

NO
YES


这个题就是判断gcd(n,m)是不是1

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main(){
    ll t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(gcd(n,m)==1){
            printf("NO
");
        }    
        else{
            printf("YES
");
        }
    } 
}

例三：
链接：https://ac.nowcoder.com/acm/contest/8755/G
来源：牛客网

神崎作为魔界之神，造人的方法是用沙子捏成人形，然后用魔法赋予其意识。

神崎有一台天平以及 $a_i\$ 个砝码，另外她还有很多个同样重的烧杯和无穷多的沙子。平日她通过这些来称量出准确重量的沙子。

她想知道能否利用这些砝码称出重量为 $x\$ 的沙子？

一共有 $q\$ 次询问。

注：烧杯的数量可以视为无穷多个。烧杯的重量是未知的，但大小可以视为无穷大，即可以装任意多的沙子。烧杯中也可以放砝码。

输入描述:

第一行一个正整数 $n\$ 。

第二行有 $n\$ 个正整数，代表砝码的重量。

接下来的一行有一个正整数 $q\$ 。

接下来的 $q\$ 行，每一行有一个正整数 $x\$ ，分别代表一次询问。

数据范围：

输出描述:

输出

行。如果能撑出重量为

的沙子，则输出"Yes"。否则输出"No"（不包含引号）。

示例1

输入

复制

输出

复制

Yes
No

说明

想要称出重量为8的沙子，可以先用两个砝码称出重量14的沙子，然后用这些沙子和一个重量6的砝码称出重量8的沙子。 
但是无论如何，显然都不能称出重量7的沙子。

题目大意就是给你n个数看能否通过加减变换变成x
这个只需要判断x%(gcd(a1,a2---a3))是否为0

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
ll a[maxn];
ll gcd(ll a,ll b){
    if(b==0){
        return a;
    }
    else{
        return gcd(b,a%b);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll p=a[1];
    for(int i=2;i<=n;i++){
        p=gcd(a[i],p);
    }
    int m;
    cin>>m;
    ll x;
    for(int i=1;i<=m;i++){
        cin>>x;
        if(x%p==0){
            printf("Yes
");
        }
        else{
            printf("No
");
        }
    }
}

链接：https://ac.nowcoder.com/acm/contest/9984/J
来源：牛客网

输入描述:

第一行一个数表示 n 。

第二行 n 个数，第 i 个数表示

输出描述:

输出一行一个数表示答案。

示例1

输入

复制

2
9 3
1 2

输出

复制

说明

 $gcd(9^1,3^2)=9 这个题就是$

我们先考虑下子问题：求 $gcd(x_1,\dots,x_n)$ , 无非就是质因数分解，然后找到大家都有的因子, 以及这个因子出现的最小次数。

举个例子： $gcd(24, 32, 36) = gcd(2^3\cdot3, 2^4, 2^2\cdot3^2)$ , 共同出现的质因子是 $2$ , 分别出现了 $3, 4, 2$ 次，那么最小次数就是 $2$ , 因此 $gcd(24, 32, 36) = 2^2 = 4$

回到本题目来，该问题中多了 $p_i$ , 我们知道 $(a^b)^c = a^{b\cdot c}$ , 那么同样地只需要在原来的子问题中找到出现了 $n$ 次的质因子的最小次数，将最小次数乘以对应的 $p_i$ 即可。

就是看看gcd(2,3,4)=gcd(2,3,2^2)就是第二个数字没有因子2,所以没有2这个贡献

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f; 
const int maxn=5e6+100;
const ll mod=1e9+7;
struct node{
    ll x;
    ll p;
}a[maxn];
ll z[maxn];
ll x[maxn]; 
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        } 
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
} 
int main(){
    memset(z,inf,sizeof(z)); 
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].p;
    } 
    for(int i=1;i<=n;i++){
        ll q=a[i].x;
        for(int j=2;j*j<=q;j++){
            ll sum=0;
            while(q%j==0){
                sum++;
                q/=j;    
            }
            if(sum){
                x[j]++;
                z[j]=min(z[j],sum*a[i].p);
            }
        }
        if(q!=1){
            z[q]=min(z[q],1ll*a[i].p);
            x[q]++;
        }
    }
    ll ans=1;
    for(ll i=1;i<=5e5;i++){
        if(x[i]>=n&&z[i]!=4557430888798830399){ 
            ans=(ans*qpow(i,z[i]))%mod;
        } 
    }
    cout<<ans<<endl;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const int N=1e4+5;
int x[N],p[N],cnt;
const int mod=1e9+7;
const int MAX=0x3f3f3f3f;

int main()
{
    ll ans=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&x[i]);
    for(int i=1;i<=n;++i) scanf("%d",&p[i]);
    
    for(int i=2;i<=10000;++i)
    { 
        cnt=MAX;
        for(int j=1;j<=n;++j)
        {
            int k=0;
            while(x[j]%i==0)
            {
                k++;
                x[j]=x[j]/i;
            }
            cnt=min(cnt,k*p[j]);
        }
        for(int r=1;r<=cnt;++r) ans=(ans%mod*i%mod)%mod;
    }
    printf("%lld
",ans%mod);
    return 0;
}