首页 > 代码库 > 2014.11.12模拟赛【最小公倍数】| vijos1047最小公倍数
2014.11.12模拟赛【最小公倍数】| vijos1047最小公倍数
最小公倍数(lcm.c/.cpp/.pas)
题目描述
给定两个正整数，求他们的最小公倍数。
样例输入
28 12
样例输出
84
数据范围
对于40%数据：1<=a,b<=10^9
对于60%的数据：1<=a,b<=10^12
对于100%数据：1<=a,b<=10^100
提示：为了略微降低题目难度，增加以下条件：
1． 输入数据保证a>=b
2． 输入数据保证a、b没有前导0
3． 输入数据保证除了在两个正整数a、b之间的空格和行末换行符以外，不存在其他非数字字符
最后友情提醒：高精除高精写二分做法风味更佳
其实就是superlcm啦……
先算出gcd(a,b)，然后lcm(a,b)=a*b/gcd(a,b)
40分是暴力，60分lcm(a,b)=a/gcd(a,b)*b,这样不会爆long long
100分就呵呵了，你只要写高精度减法、乘法、除法就好了
给现场怒写高精度还A了的hzwer跪了
这其实可以当成模板来用
#define mx 300#include<cstdio>#include<iostream>using namespace std; struct gaojing{ int len; int a[mx+10];};//定义高精度非负数类型gaojing zero,one;inline void set0(gaojing &s){ s.len=1; for (int i=1;i<=mx+5;i++)s.a[i]=0;}inline void inputn(gaojing &a){ set0(a); char ch=getchar(); while (ch<‘0‘||ch>‘9‘)ch=getchar(); while (ch>=‘0‘&&ch<=‘9‘) { a.a[a.len++]=ch-‘0‘; ch=getchar(); } a.len--; int change[mx+15]; for (int i=1;i<=a.len;i++) change[i]=a.a[i]; for (int i=1;i<=a.len;i++) a.a[i]=change[a.len-i+1]; while (a.a[a.len]==0)a.len--;} inline void put(gaojing a){ for (int i=a.len;i>=1;i--)printf("%d",a.a[i]); printf("\n");}inline bool operator < (const gaojing &a,const gaojing &b){ if (a.len<b.len)return 1; if (a.len>b.len)return 0; for (int i=a.len;i>=1;i--) { if (a.a[i]<b.a[i])return 1; if (a.a[i]>b.a[i])return 0; } return 0;}inline bool operator == (const gaojing &a,const gaojing &b){ if (a.len!=b.len)return 0; for (int i=a.len;i>=1;i--) { if (a.a[i]!=b.a[i])return 0; } return 1;}inline gaojing max(const gaojing &a,const gaojing &b){ if (a<b)return b; else return a;}inline gaojing min(const gaojing &a,const gaojing &b){ if (a<b)return a; else return b;} inline gaojing operator + (const gaojing &a,const gaojing &b){ gaojing c;set0(c); int maxlen=max(a.len,b.len); for (int i=1;i<=maxlen;i++) { c.a[i]=c.a[i]+a.a[i]+b.a[i]; if (c.a[i]>=10) { c.a[i+1]+=c.a[i]/10; c.a[i]%=10; } } c.len=maxlen+4; while (!c.a[c.len]&&c.len>1) c.len--; return c;}inline gaojing operator - (const gaojing &a,const gaojing &b){ gaojing c;set0(c); gaojing d;d=a; for (int i=1;i<=b.len;i++) { c.a[i]=d.a[i]-b.a[i]; if (c.a[i]<0) { c.a[i]+=10; int now=i+1; while (!d.a[now]) { d.a[now]=9; now++; } d.a[now]--; } } for (int i=b.len+1;i<=d.len;i++)c.a[i]=d.a[i]; c.len=d.len; while (c.a[c.len]==0&&c.len>1)c.len--; return c;} inline gaojing operator * (const gaojing &a,const gaojing &b){ gaojing c;set0(c); for(int i=1;i<=a.len;i++) for (int j=1;j<=b.len;j++) c.a[i+j-1]+=a.a[i]*b.a[j]; c.len=a.len+b.len+5; for (int i=1;i<=c.len;i++) { c.a[i+1]+=c.a[i]/10; c.a[i]%=10; } while (!c.a[c.len]&&c.len>1)c.len--; return c;}inline void div_by_2(gaojing &a){ for (int i=a.len;i>=1;i--) { if (a.a[i]&1 && i!=1)a.a[i-1]+=10; a.a[i]/=2; } while (!a.a[a.len]&&a.len>1)a.len--;}inline gaojing operator / (gaojing a,const gaojing &b){ gaojing l,r,ans; set0(l);l.len=1; set0(r);r=a; set0(ans);ans.len=1; while (l<r||l==r) { gaojing mid=l+r; div_by_2(mid); if(mid*b==a)return mid; if(mid*b<a){ans=mid;l=mid+one;} if(a<mid*b)r=mid-one; } return ans;}inline void chushihua(){ set0(zero); zero.len=1; set0(one);one.len=1;one.a[1]=1;}inline gaojing gcd(const gaojing &a,const gaojing &b){ if (b==zero)return a; return gcd(b,a-a/b*b);}int main(){ gaojing a,b; chushihua(); inputn(a); inputn(b); put(a/gcd(a,b)*b);}
2014.11.12模拟赛【最小公倍数】| vijos1047最小公倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。