cf1511B. GCD Length

cf1511B. GCD Length

题意:

定义gcd(x,y) = z
现在给你a,b,c三个数字,含义分别是
不带前导0的x是由a个数字构成的
不带前导0的y是由b个数字构成的
不带前导0的z是由c个数字构成的

题解:

很明显构造题,但是我想不出来。。
我们想控制gcd的长度为c,
我们知道100和99的gcd为1,100和90的gcd为10,100和1000的gcd为100(利用100…0和9…90…0,我们可以方便控制gcd长度的数)

所以构造只需分两种情况考虑:
1.c=min(a,b),代表c的长度等于其中一个,那么较大的数可以是较小的数的倍数,所以我们构造出来一个10 ^ a和10 ^ b就行
2.c!=min(a,b),那么我们控制c的长度时,可以将一个数设为99900…0,一个数设为1000…,前一个数中所给出来的0的个数+1就是c的长度
比赛时想不到啊
还可以更简单:
x就是10(a-1) + 10(c-1)
y就是10(b-1)
gcd(x,y) = 10(c-1)
len(10(c-1)) = c

代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		 int x,y,z,a,b,c,n=0;
		cin>>a>>b>>c;
      	x=pow(10,a-1)+pow(10,c-1);
      	y=pow(10,b-1);
     	cout<<x<<" "<<y<<"\n";
      }
      return 0;
}
/*
3 5 2
110
10000
*/ 
上一篇:Tigase数据库结构(1)


下一篇:剑指 Offer 17. 打印从1到最大的n位数