「考后欢乐赛」最小公倍数

2014年11月12日4,8430

题目描述

给定两个正整数，求他们的最小公倍数。

样例输入

28 12

样例输出

数据范围

对于40%数据：1<=a,b<=10^9

对于60%的数据：1<=a,b<=10^12

对于100%数据：1<=a,b<=10^100

提示：为了略微降低题目难度，增加以下条件：

输入数据保证a>=b
输入数据保证a、b没有前导0
输入数据保证除了在两个正整数a、b之间的空格和行末换行符以外，不存在其他非数字字符

最后友情提醒：高精除高精写二分做法风味更佳

对于这种丧病的题，我只能说 ni ma 哔

更相减损术求gcd，lcm=a*b/gcd(a,b)

然后上高精度。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<queue>
#define mod 1000000007
#define inf 2000000000
#define ll long long 
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int cnt;
char ch[105];
struct data
{
	int v[10005],l;
	data(){
		memset(v,0,sizeof(v));
		l=0;
	}
}a,b;
void print(data a)
{
	for(int i=a.l;i;i--)
		printf("%d",a.v[i]);
	printf("\n");
}
bool operator>(data a,data b)
{
	if(a.l>b.l)return 1;
	if(a.l<b.l)return 0;
	for(int i=a.l;i;i--)
		if(a.v[i]>b.v[i])return 1;
		else if(a.v[i]<b.v[i])return 0;
	return 0;
}
data operator*(data a,data b)
{
	data c;
	for(int i=1;i<=a.l;i++)
		for(int j=1;j<=b.l;j++)
			c.v[i+j-1]+=a.v[i]*b.v[j];
	for(int i=1;i<=a.l+b.l;i++)
	{
		if(c.v[i]>=10)
		{
			c.v[i+1]+=c.v[i]/10;
			c.v[i]%=10;
		}
		if(c.v[i])c.l=i;
	}
	return c;
}
data operator-(data a,data b)
{
	data c;
	for(int i=1;i<=a.l;i++)
	{
		c.v[i]=a.v[i]-b.v[i];
		if(c.v[i]<0)
		{
			c.v[i]+=10;
			a.v[i+1]--;
		}
	}
	c.l=a.l;
	while(!c.v[c.l]&&c.l)c.l--;
	return c;
}
data operator+(data a,data b)
{
	data c;
	c.l=max(a.l,b.l);
	for(int i=1;i<=c.l;i++)
		c.v[i]=a.v[i]+b.v[i];
	for(int i=1;i<=c.l;i++)
		if(c.v[i]>=10)
		{
			c.v[i]%=10;
			c.v[i+1]++;
		}
	while(c.v[c.l+1])c.l++;
	return c;
}
void div(data &a)
{
	for(int i=1;i<=a.l;i++)
	{
		if(a.v[i]&1)a.v[i-1]+=5;
		a.v[i]>>=1;  
	}
	while(!a.v[a.l]&&a.l)a.l--;
}
void mul(data &a)
{
	for(int i=1;i<=a.l;i++)
	{
		a.v[i]<<=1;
		if(a.v[i-1]>=10)
		{
			a.v[i-1]%=10;
			a.v[i]++;
		}
	}
	if(a.v[a.l]>=10)
	{
		a.v[a.l]%=10;
		a.v[a.l+1]++;
		a.l++;
	}
}
void solve()
{
	data gcd,mid,l,r=a*b,T=r;
	while(1)
	{
		if(a.v[1]%2==0&&b.v[1]%2==0)div(a),div(b),cnt++;
		else if(a.v[1]%2==0)div(a);
		else if(b.v[1]%2==0)div(b);
		else if(a>b){a=a-b;if(!a.l){while(cnt--)mul(b);gcd=b;break;}}
		else {b=b-a;if(!b.l){while(cnt--)mul(a);gcd=a;break;}}
	}
	while(r>l)
	{
		data t=r-l;
		if(t.l==1&&t.v[1]==1)break;
	    mid=l+r;div(mid);
		if(mid*gcd>T)r=mid;
		else l=mid;
	}
	if(r*gcd>T)print(l);
	else print(r);
}
int main()
{
	scanf("%s",ch+1);
	a.l=strlen(ch+1);
	for(int i=1;i<=a.l;i++)
		a.v[i]=ch[a.l-i+1]-'0';
	scanf("%s",ch+1);
	b.l=strlen(ch+1);
	for(int i=1;i<=b.l;i++)
		b.v[i]=ch[b.l-i+1]-'0';
	solve();
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#include<queue>

#define mod 1000000007

#define inf 2000000000

#define ll long long

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int cnt;

char ch[105];

struct data

{

int v[10005],l;

data(){

memset(v,0,sizeof(v));

l=0;

}

}a,b;

void print(data a)

{

for(int i=a.l;i;i--)

printf("%d",a.v[i]);

printf("\n");

}

bool operator>(data a,data b)

{

if(a.l>b.l)return 1;

if(a.l<b.l)return 0;

for(int i=a.l;i;i--)

if(a.v[i]>b.v[i])return 1;

else if(a.v[i]<b.v[i])return 0;

return 0;

}

data operator*(data a,data b)

{

data c;

for(int i=1;i<=a.l;i++)

for(int j=1;j<=b.l;j++)

c.v[i+j-1]+=a.v[i]*b.v[j];

for(int i=1;i<=a.l+b.l;i++)

{

if(c.v[i]>=10)

{

c.v[i+1]+=c.v[i]/10;

c.v[i]%=10;

}

if(c.v[i])c.l=i;

}

return c;

}

data operator-(data a,data b)

{

data c;

for(int i=1;i<=a.l;i++)

{

c.v[i]=a.v[i]-b.v[i];

if(c.v[i]<0)

{

c.v[i]+=10;

a.v[i+1]--;

}

c.l=a.l;

while(!c.v[c.l]&&c.l)c.l--;

return c;

}

data operator+(data a,data b)

{

data c;

c.l=max(a.l,b.l);

for(int i=1;i<=c.l;i++)

c.v[i]=a.v[i]+b.v[i];

for(int i=1;i<=c.l;i++)

if(c.v[i]>=10)

{

c.v[i]%=10;

c.v[i+1]++;

}

while(c.v[c.l+1])c.l++;

return c;

}

void div(data &a)

{

for(int i=1;i<=a.l;i++)

{

if(a.v[i]&1)a.v[i-1]+=5;

a.v[i]>>=1;

}

while(!a.v[a.l]&&a.l)a.l--;

}

void mul(data &a)

{

for(int i=1;i<=a.l;i++)

{

a.v[i]<<=1;

if(a.v[i-1]>=10)

{

a.v[i-1]%=10;

a.v[i]++;

}

if(a.v[a.l]>=10)

{

a.v[a.l]%=10;

a.v[a.l+1]++;

a.l++;

}

void solve()

{

data gcd,mid,l,r=a*b,T=r;

while(1)

{

if(a.v[1]%2==0&&b.v[1]%2==0)div(a),div(b),cnt++;

else if(a.v[1]%2==0)div(a);

else if(b.v[1]%2==0)div(b);

else if(a>b){a=a-b;if(!a.l){while(cnt--)mul(b);gcd=b;break;}}

else {b=b-a;if(!b.l){while(cnt--)mul(a);gcd=a;break;}}

}

while(r>l)

{

data t=r-l;

if(t.l==1&&t.v[1]==1)break;

mid=l+r;div(mid);

if(mid*gcd>T)r=mid;

else l=mid;

}

if(r*gcd>T)print(l);

else print(r);

}

int main()

{

scanf("%s",ch+1);

a.l=strlen(ch+1);

for(int i=1;i<=a.l;i++)

a.v[i]=ch[a.l-i+1]-'0';

scanf("%s",ch+1);

b.l=strlen(ch+1);

for(int i=1;i<=b.l;i++)

b.v[i]=ch[b.l-i+1]-'0';

solve();

return 0;

}

« 「codechefSUBGCD」Subarray GCD 「BZOJ1089」[SCOI2003] 严格n元树 »

hzwer.com _ Home | http://hzwer.com

「考后欢乐赛」最小公倍数

分类目录

热门文章

Myfriends

近期评论