UVA数学入门训练Round1[6]

题意：输入g和l，找到a和b，gcd(a,b)=g,lacm(a,b)=l,a<b且a最小

g不能整除l时无解，否则一定g,l最小

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int T,g,l;

int main(int argc, const char * argv[]){

    T=read();

    while(T--){

        g=read();l=read();

        if(l%g) printf("-1\n");

        else printf("%d %d\n",g,l);

    }

    return ;

}

PS:Luogup1029求数量的话可以依据a*b=g*l枚举

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

ll g,l;

int cnt=;

inline int gcd(int a,int b){

    return b==?a:gcd(b,a%b);

}

int main(int argc, const char * argv[]) {

    g=read();l=read();

    ll n=g*l;

    for(ll i=g;i<=l;i++){

        if(n%i) continue;

        ll j=n/i;

        if(gcd(i,j)==g) cnt++;

    }

    printf("%d",cnt);

    return ;

}

UVA - 11889

Benefit

题意：输入A和C，求最小的B使lcm(A,B)=C

用唯一分解定理想

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int a,l,T;

inline int gcd(int a,int b){return b==?a:gcd(b,a%b);}

int main(int argc, const char * argv[]) {

    T=read();

    while(T--){

        a=read();l=read();

        if(l%a) printf("NO SOLUTION\n");

        else{

            int b=l/a,g=gcd(a,b),t=;

            while(g!=){

                t*=g;

                a/=g;

                g=gcd(a,b);

            }

            printf("%d\n",b*t);

        }

    }

    return ;

}

UVA - 10943

How do you add?

题意：k个不超过n的非负整数加起来和为n有几种方案

完全背包

f[i][j]表示i个数加起来和为j

转移可以从O(n)变O(1)

可以是f[i-1][j]+0,也可以是f[i][j-1]+1

f[i][j]=(f[i-1][j]+f[i][j-1])%MOD;

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=,MOD=1e6;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,f[N][N];

void dp(){

    for(int i=;i<=;i++) f[i][]=;

    for(int i=;i<=;i++)

        for(int j=;j<=;j++)

            f[i][j]=(f[i-][j]+f[i][j-])%MOD;

}

int main(int argc, const char * argv[]) {

    dp();

    while((n=read())){

        m=read();

        printf("%d\n",f[m][n]);

    }

    return ;

}

UVA - 10791

Minimum Sum LCM

题意：输入n，求至少两个正整数，使lcm=n

唯一分解定理分解后就是最优解，注意素数

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n;

ll sol(int n){

    if(n==) return ;

    int cnt=,m=sqrt(n)+;

    ll ans=;

    for(int i=;i<=m&&n!=;i++) if(n%i==){

        cnt++;

        ll d=;

        while(n%i==) n/=i,d*=i;

        ans+=d;

    }

    if(n>) cnt++,ans+=n;

    if(cnt==) return ans+;

    else return ans;

}

int main(int argc, const char * argv[]) {

    int cas=;

    while(scanf("%d",&n)!=EOF&&n){

        printf("Case %d: %lld\n",++cas,sol(n));

    }

    return ;

}

UVA - 10780

Again Prime? No Time.

题意：输入n和m，求最大的k使m^k整除n！

唯一分解定理裸

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=1e4+;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int T,m,n,e1[N],e2[N],p[N],vis[N],cnt=;

void era(int n){

    int m=sqrt(n)+;

    for(int i=;i<=m;i++) if(!vis[i])

        for(int j=i*i;j<=n;j+=i) vis[j]=;

    for(int i=;i<=n;i++) if(!vis[i]) p[++cnt]=i;

}

void divide(int n,int e[]){

    for(int i=;i<=cnt&&n!=;i++) if(n%p[i]==){

        int d=;

        while(n%p[i]==) n/=p[i],d++;

        e[i]+=d;

    }

}

int main(int argc, const char * argv[]){

    era();

    T=read();int cas=;

    while(T--){

        printf("Case %d:\n",++cas);

        memset(e1,,sizeof(e1));

        memset(e2,,sizeof(e2));

        m=read();n=read();

        divide(m,e1);

        for(int i=;i<=n;i++) divide(i,e2);

        int flag=,k=,len=max(m,n);

        for(int i=;i<=len;i++){//printf("%d  %d %d\n",p[i],e1[i],e2[i]);

            if(e1[i]>e2[i]){flag=;printf("Impossible to divide\n");break;}

            if(e2[i]!=&&e1[i]!=) k=min(k,e2[i]/e1[i]);

        }

        if(!flag) printf("%d\n",k);

    }

    return ;

}

秒客网

UVA数学入门训练Round1[6]

相关文章