首页 > 代码库 > UVA数学入门训练Round1[6]
UVA数学入门训练Round1[6]
| UVA - 11388 GCD LCM |
题意：输入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=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;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 0;}
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=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}ll g,l;int cnt=0;inline int gcd(int a,int b){ return b==0?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 0;}
| 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=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int a,l,T;inline int gcd(int a,int b){return b==0?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=1; while(g!=1){ t*=g; a/=g; g=gcd(a,b); } printf("%d\n",b*t); } } return 0;}
| 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=105,MOD=1e6;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,f[N][N];void dp(){ for(int i=0;i<=100;i++) f[i][0]=1; for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) f[i][j]=(f[i-1][j]+f[i][j-1])%MOD;}int main(int argc, const char * argv[]) { dp(); while((n=read())){ m=read(); printf("%d\n",f[m][n]); } return 0;}
| 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=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n;ll sol(int n){ if(n==1) return 2; int cnt=0,m=sqrt(n)+1; ll ans=0; for(int i=2;i<=m&&n!=1;i++) if(n%i==0){ cnt++; ll d=1; while(n%i==0) n/=i,d*=i; ans+=d; } if(n>1) cnt++,ans+=n; if(cnt==1) return ans+1; else return ans;}int main(int argc, const char * argv[]) { int cas=0; while(scanf("%d",&n)!=EOF&&n){ printf("Case %d: %lld\n",++cas,sol(n)); } return 0;}
| 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+5;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int T,m,n,e1[N],e2[N],p[N],vis[N],cnt=0;void era(int n){ int m=sqrt(n)+1; for(int i=2;i<=m;i++) if(!vis[i]) for(int j=i*i;j<=n;j+=i) vis[j]=1; for(int i=2;i<=n;i++) if(!vis[i]) p[++cnt]=i;}void divide(int n,int e[]){ for(int i=1;i<=cnt&&n!=1;i++) if(n%p[i]==0){ int d=0; while(n%p[i]==0) n/=p[i],d++; e[i]+=d; }}int main(int argc, const char * argv[]){ era(10000); T=read();int cas=0; while(T--){ printf("Case %d:\n",++cas); memset(e1,0,sizeof(e1)); memset(e2,0,sizeof(e2)); m=read();n=read(); divide(m,e1); for(int i=1;i<=n;i++) divide(i,e2); int flag=0,k=100000,len=max(m,n); for(int i=1;i<=len;i++){//printf("%d %d %d\n",p[i],e1[i],e2[i]); if(e1[i]>e2[i]){flag=1;printf("Impossible to divide\n");break;} if(e2[i]!=0&&e1[i]!=0) k=min(k,e2[i]/e1[i]); } if(!flag) printf("%d\n",k); } return 0;}
UVA数学入门训练Round1[6]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。