数论小测

hdu5207Greatest Greatest Common Divisor

题意

​ 给定n个数求任意俩个数得最大公因数

思路

​ 因为之前写过求俩个数得最小公倍数，所以这道问题迎刃而解，就是枚举他们得因数，用数组记录每个因数出现的次数，最后从大到小找出现俩次得那个数，输出即可。

代码1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int main(){
    int t;
    cin>>t;
    int id=0;
    while(t--){
        memset(a,0,sizeof a);
        int n;
        scanf("%d",&n);
        int maxx=-1;
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            maxx=max(x,maxx);
            for(int i=1;i*i<=x;i++){
                if(!(x%i)){
                    a[i]++;
                    if(x/i!=i){
                        a[x/i]++;
                    }
                }
            }
        }
        int ans=0;
        for(int i=maxx;i>=1;i--){
            if(a[i]>=2) {
                ans=i;
                break;
            }
        }
        printf("Case #%d: %d\n",++id,ans);
    }
}

但后来听大佬的正解，发现是先预处理出所有数的因数直接在循环中累计个数就🆗了。

代码2

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int> c[maxn];
int v[maxn];
void init(){
    for(int i=1;i<maxn;i++){
        for(int j=i;j<maxn;j+=i){
            c[j].push_back(i);
        }
    }
}
int main(){
    int t;
    cin>>t;
    init();
    int id=0;
    while(t--){
	memset(v,0,sizeof v);
        int n;
        cin>>n;
        int maxx=-1;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            maxx=max(maxx,x);
            for(int j=0;j<c[x].size();j++){
                v[c[x][j]]++;
            }
        }
        int x=0;
        for(int i=maxx;i>=1;i--){
            if(v[i]>=2){
                x=i;
                break;
            }
        }
        printf("Case #%d: %d\n",++id,x);
    }

    //system("pause");
    return 0;
}

HDU5698瞬间移动

题意

​ 无限大的矩形，从(1,1)每次可以瞬移到右下方格的任意一个格子，求最后到达(n,m)的方案数。

思路

​ 枚举中间走的步数i，中间走的最大步数必然是min(m-2,n-2)步，然后开始枚举。

代码1

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=1e9+7;
const int maxn=1e6+10;
int jc[maxn],jcinv[maxn];
int C(int n,int m){
    return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int ksm(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1) c=1ll*c*a%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
int main(){
    jc[0]=1,jcinv[0]=1;
    jc[1]=1,jcinv[1]=1;
    for(int i=2;i<=maxn;i++){
        jc[i]=1ll*jc[i-1]*i%mod;
        jcinv[i]=ksm(jc[i],mod-2);
    }
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int ans=0;
        for(int i=0;i<=min(n-2,m-2);i++){
            ans=(ans+1ll*C(n-2,i)*C(m-2,i)%mod)%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

网上查阅的答案为C(n+m-4,n-2)

代码2

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e6+10;
int jc[maxn],jcinv[maxn];
int C(int n,int m){
    return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int ksm(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1) c=1ll*c*a%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
int main(){
    jc[0]=1,jcinv[0]=1;
    jc[1]=1,jcinv[1]=1;
    for(int i=2;i<=maxn;i++){
        jc[i]=1ll*jc[i-1]*i%mod;
        jcinv[i]=ksm(jc[i],mod-2);
    }
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        printf("%d\n",C(n+m-4,n-2));
    }
    return 0;
}

cfdiv2 Modified GCD

题意

​ 给定俩个数a和b，然后给m个查询，每行俩个整数x和y，表示查询x到y之间最大a和b的因数。

思路

​ 这也太简单了，直接预处理出gcd(a,b)的所有因数，排序，二分查找第一个比b大的数的下标位置，在把这个位置向后倒退一步，再判断是否为x-y这个区间内，是则输出，否则输出-1.

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int c[maxn];
int main(){
    int a,b;
    cin>>a>>b;
    int x=__gcd(a,b);
    int id=0;
    for(int i=1;i*i<=x;i++){
        if(x%i==0){
            c[++id]=i;
            if(x/i!=i) c[++id]=x/i;
        }
    }
    sort(c+1,c+id+1);
    // for(int i=1;i<=id;i++) cout<<c[i]<<endl;
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        x=upper_bound(c+1,c+id+1,b)-c;
        x--;
        if(c[x]<=b&&c[x]>=a) cout<<c[x]<<endl;
        else cout<<-1<<endl;
    }
    //system("pause");
    return 0;
}

BZOJ2818 Gcd

题意

​ 给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

思路

​ 由题意得：

​ gcd(x,y)=p

​ gcd(x/p,y/p)=1

​ 所以枚举每个素数(代码中m表示n以内的素数个数)，求n/p以内俩俩互质对数的个数，最后再乘p即为所求的gcd(x,y)=p ,因为俩个数顺序变换也算，所以最后乘2，另外(1,1)是个特殊的存在所以在计算的时候减去最后再加即可。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e7+10;
int v[maxn],prime[maxn],phi[maxn];
long long sum[maxn];
int m;
void euler(int n){
    memset(v,0,sizeof(v));
    m=0;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i;
            prime[++m]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=m;j++){
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
}
int main(){
    int n;
    cin>>n;
    euler(n);
    for(int i=1;i<=n;i++)
        sum[i]=phi[i]+sum[i-1];
    long long ans=0;
    for(int i=1;i<=m;i++)
        ans+=(sum[n/prime[i]]-1);
    printf("%lld\n",2*ans+m);
    //system("pause");
}

POJ1061青蛙的约会

题意

​ 有俩个青蛙A和B，在一个长为l的环形上，初始时A在x处每次跳m米，B在y处每次跳n米，求最后需要跳几次才能相遇。

思路

​ 很明显一个扩展欧几里得的模板题。

​ 因为(x+mt)%l=(y+nt)%l,

​ 移项得(m-n)t%l=(y-x)%l

​ 得(m-n)t+lk=(y-x)

​ 对应扩展欧几里得中(ax+by=c) ， (m-n)为a，l为b ，c为(y-x).

​ 最后求得得数为x得解，因为可能为负数所以最后((x*c/gcd(a,b)%l)+l)%l。

代码

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
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,x,y);
    ll z=x;x=y;y=z-y*(a/b);
    return d;
}
int main(){
    ll n,m,x,y,l;
    while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)){
        ll t,k;
        ll gcd=exgcd(m-n,l,t,k);
        ll c=(y-x)/gcd;
        if((y-x)%gcd) puts("Impossible");
        else printf("%lld\n",((t*c)%l+l)%l);
    }
}