| UVA - 11388 |
题意：输入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 |
题意：输入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 |
题意：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 |
题意：输入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 |
题意： 输入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 ;
}