2016年第七届蓝桥杯省赛C语言B组

2016年第七届蓝桥杯省赛C语言B组

2016年第七届蓝桥杯省赛C语言B组

题目来源：蓝桥杯
作者：GGG166
第一题
题目：煤球数目
有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形），
第三层6个（排列成三角形），
第四层10个（排列成三角形），
…
如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：171700

思路1：
很明显找出每一层的规律，就是每一层煤球的个数等于它的层数乘以层数+1在除以二，最后把100层的煤球加起来（见代码1-1）。
代码1-1：

#include<iostream>
using namespace std;int main()
{int f[101],sum=0;//f为层数 for(int i=1;i<=100;i++){ f[i]=(i*(i+1))/2;} for(int i=1;i<=100;i++){ sum+=f[i];} cout<<sum<<endl;return 0;
}

思路2：
很明显，第一层与的二层相差2，第二层与的三层相差3，第三层与的四层相差4，经过推理第i-1层与第i层相差i。再计算出100层的并相加就行了。
代码1-2：

#include<iostream>
using namespace std;int main()
{int sum=1,j=2,i=1; //i表示层数，j表示差值 for(int k=2;k<=100;k++){sum+=(i+j);i+=j;j++;}cout<<sum<<endl;return 0;
}

第二题
题目：生日蜡烛
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：26

思路：
我就从1到100岁之间，来测试他吹熄了蜡烛的根数，当i~ j岁时统计数目且数目为236就找到了并输出i（见代码2-1），或者用等差数列来求就可以得到公式：（i+j）*（j-1+1）/2=236,并输出i（见代码2-2）。
代码2-1：

#include<iostream>
using namespace std;int main()
{int sum=0;//蜡烛的根数for(int i=1;i<100;i++){for(int j=i;j<100;j++){sum+=j;if(sum==236){//找到了cout<<i<<endl;break;}}sum=0;//蜡烛的根数归0}return 0;  
}

代码2-2：

#include<iostream>
using namespace std;int main()
{for(int i=1;i<100;i++){for(int j=i;j<100;j++){if(2*236==(i+j)*(j-i+1)){//找到了cout<<i<<endl;break;}}}return 0;  
}

第三题
题目：凑算式
B DEF
A + — + ------- = 10
C GHI
（如果显示有问题，可以参见【图1.jpg】）

这个算式中A~ I 代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。

答案：29

思路1：
用枚举法，列举出来A~ I，再来计算（见代码3-1），该方法简单，但是在写代码时小细节很容易出错，本人不建议。
代码：

#include<iostream>
using namespace std;
int main()
{int a,b,c,d,e,f,i,g,h,cnt=0;for(a=1;a<10;a++)for(b=1;b<10;b++)if(b!=a)for(c=1;c<10;c++)if(c!=a && c!=b) for(d=1;d<10;d++)if(d!=a && d!=b && d!=c)for(e=1;e<10;e++)if(e!=a && e!=b && e!=c && e!=d)for(f=1;f<10;f++)if(f!=a &&f!=b &&f!=c &&f!=d &&f!=e )for(g=1;g<10;g++)if(g!=a &&g!=b &&g!=c &&g!=d &&g!=e &&g!=f )for(h=1;h<10;h++)if(h!=a &&h!=b &&h!=c &&h!=d &&h!=e &&h!=f &&h!=g )for(i=1;i<10;i++)if(i!=a &&i!=b &&i!=c &&i!=d &&i!=e &&i!=f &&i!=g &&i!=h){//printf("%d%d%d%d%d%d%d%d%dn",a,b,c,d,e,f,g,h,i);int k1=(a*c*(g*100+h*10+i)+b*(g*100+h*10+i)+c*(d*100+e*10+f))/(c*(g*100+h*10+i));int k2=(a*c*(g*100+h*10+i)+b*(g*100+h*10+i)+c*(d*100+e*10+f))%(c*(g*100+h*10+i));if(k1==10 &&k2==0){//printf("%d+%d/%d+%d%d%d/%d%d%d",a,b,c,d,e,f,g,h,i);cnt++;}}cout<<cnt<<endl;return 0;
}

思路2：
用全排列来做，注意下标为与数组的对应关系即可（见代码3-2）。本人建议用全排列来解决，最后在给大家手工全排列的原理（见代码3-3）。
代码3-2：

#include<iostream>
#include<algorithm>
using namespace std;int a[9]={1,2,3,4,5,6,7,8,9};
int ans=0;
int main(){do{int x=a[3]*100+a[4]*10+a[5];int y=a[6]*100+a[7]*10+a[8];		if(a[0]+(a[1]*y+a[2]*x)/(a[2]*y)==10 && (a[1]*y+a[2]*x)%(a[2]*y)==0){ans++;}}while(next_permutation(a,a+9));//next_permutation()全排列函数 cout<<ans<<endl;return 0;
}

代码3-3：

#include<iostream>
using namespace std;int a[9]={1,2,3,4,5,6,7,8,9};
int ans=0;
void f(int k){if(k==9){//结束条件int x=a[3]*100+a[4]*10+a[5];int y=a[6]*100+a[7]*10+a[8];		if(a[0]+(a[1]*y+a[2]*x)/(a[2]*y)==10 && (a[1]*y+a[2]*x)%(a[2]*y)==0){ans++;			}return ;}for(int i=k;i<9;i++){int t=a[i];a[i]=a[k];a[k]=t;//交换f(k+1);//递归t=a[i];a[i]=a[k];a[k]=t;//回溯}
} 
int main()
{f(0);cout<<ans<<endl;return 0;	
}

第四题
题目：快速排序
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。

#include <stdio.h>void swap(int a[], int i, int j)
{int t = a[i];a[i] = a[j];a[j] = t;
}int partition(int a[], int p, int r)
{int i = p;int j = r + 1;int x = a[p];while(1){while(i<r && a[++i]<x);while(a[--j]>x);if(i>=j) break;swap(a,i,j);}______________________;//填空return j;
}void quicksort(int a[], int p, int r)
{if(p<r){int q = partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);}
}int main()
{int i;int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};int N = 12;quicksort(a, 0, N-1);for(i=0; i<N; i++) printf("%d ", a[i]);printf("n");return 0;
}

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

答案：swap(a,p,j)

思路：
学过算法的很快很容易的得出答案，因为是学过并写过快排。言归正传，快数排序就像上面说的一样，再来看函数quicksort的参数是数组a，左端点p，右端点r，p<r就用q来记录位置，在调用本身给左右子区间排序；再看partition函数参数也是数组a，左端点p，右端点r，再用i记录左端点，j记录右端点，x记录左端点的值，在一直循环到i<j时结束，在分别循环比较从左到右和从右到左两部分，不满足条件就交换，最后在返回j，这样就不难看出答案了，因为还没有让其左边的元素都不大于它、其右边的元素都不小于它，就应该是交换第一个与上面循环中的最后一个。最后带入运行检查。
代码4：

#include <stdio.h>void swap(int a[], int i, int j)
{int t = a[i];a[i] = a[j];a[j] = t;
}int partition(int a[], int p, int r)
{int i = p;int j = r + 1;int x = a[p];while(1){while(i<r && a[++i]<x);while(a[--j]>x);if(i>=j) break;swap(a,i,j);}swap(a,p,j);//填空return j;
}void quicksort(int a[], int p, int r)
{if(p<r){int q = partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);}
}int main()
{int i;int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};int N = 12;quicksort(a, 0, N-1);for(i=0; i<N; i++) printf("%d ", a[i]);printf("n");return 0;
}

第五题
题目：抽签
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
…
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
…
(以下省略，总共101行)

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024void f(int a[], int k, int m, char b[])
{int i,j;if(k==N){ b[M] = 0;if(m==0) printf("%sn",b);return;}for(i=0; i<=a[k]; i++){for(j=0; j<i; j++) b[M-m+j] = k+'A';______________________;  //填空位置}
}
int main()
{	int  a[N] = {4,2,2,1,1,3};char b[BUF];f(a,0,M,b);return 0;
}

仔细阅读代码，填写划线部分缺少的内容。
注意：不要填写任何已有内容或说明性文字。

答案：f(a,k+1,m-j,b)

思路：
看f函数的参数有数组a、数k和m,还有一个字符串，定义了i和j用于循环，有一个判断，看内容一定用到了递归，从而得出k为国家的下标、m为取得人数；在看循环体中的内容，不出意外应该要填成递归的形式就可以得出–f(a,b),然后找下一个国家，人数下降，就可以得出答案了。最后带入运行检查。
代码5：

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024void f(int a[], int k, int m, char b[])
{int i,j;if(k==N){ b[M] = 0;if(m==0) printf("%sn",b);return;}for(i=0; i<=a[k]; i++){for(j=0; j<i; j++) b[M-m+j] = k+'A';f(a,k+1,m-j,b) ;  //填空位置}
}
int main()
{	int  a[N] = {4,2,2,1,1,3};char b[BUF];f(a,0,M,b);return 0;
}

第六题
题目：方格填数
如下的10个格子

  +--+--+--+|  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：1580

思路1：
用数组来表示格子如下：

用全排列排序，在按要求执行（见代码6-1）。
代码6-1：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int a[10]={0,1,2,3,4,5,6,7,8,9};
bool check(){if(abs(a[0]-a[1])==1||abs(a[0]-a[3])==1||abs(a[0]-a[4])==1||abs(a[0]-a[5])==1|| abs(a[1]-a[2])==1||abs(a[1]-a[4])==1||abs(a[1]-a[5])==1||abs(a[1]-a[6])==1|| abs(a[2]-a[5])==1||abs(a[2]-a[6])==1|| abs(a[3]-a[4])==1||abs(a[3]-a[7])==1||abs(a[3]-a[8])==1|| abs(a[4]-a[5])==1||abs(a[4]-a[7])==1||abs(a[4]-a[8])==1||abs(a[4]-a[9])==1|| abs(a[5]-a[6])==1||abs(a[5]-a[8])==1||abs(a[5]-a[9])==1|| abs(a[6]-a[9])==1|| abs(a[7]-a[8])==1|| abs(a[8]-a[9])==1)return false;return true;
}
int main(){int ans = 0;do{if(check()){ans++;}}while(next_permutation(a,a+10));cout<<ans<<endl;return 0;
}

思路2：
补全格子成5*6的格子如图：

然后在抓取0~9替换红色区域，如果四周差的绝对值不为1就可以，如果为1就提前结束（见代码6-2）。在数据规模不大或填空题（全排列的时间复杂度允许–本人认为不超过10^10）的情况下，我建议用思路1，其他的用成思路2。
代码6-2：

#include<iostream>
#include<cmath>
using namespace std;int a[5][6],vis[10],ans=0;
bool check(int x,int y){ for(int i=x-1;i<=x+1;i++){for(int j=y-1;j<=y+1;j++){if(abs(a[x][y]-a[i][j])==1)return false;}}return true;	
}
void f(int x,int y){if(x==3 && y==4){ //结束条件 ans++;return ;}for(int i=0;i<10;i++){if(vis[i]==0){a[x][y]=i;if(!check(x,y)){a[x][y]=-100;continue;}vis[i]=1;//标记 //递归 if(y==4) f(x+1,1);else     f(x,y+1);vis[i]=0;//回溯 a[x][y]=-10;}}
}
int main()
{for(int i=0;i<5;i++){//初始化a数组 for(int j=0;j<6;j++){a[i][j]=-100; 	}		    }		f(1,2);cout<<ans<<endl;
}

第七题
题目：剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：116

思路：
在12张看出一个数组，在选取5个出来，看他们上下左右是否相连，是则答案+1。在这里本人用7个0和5个1来表示的（也可以用1~12来全排列选固定的5个），同时再用一个数组来标记也选取，循环检查是否连通（见代码7）。
代码7：

#include<iostream>
#include<algorithm>
using namespace std;int a[]={0,0,0,0,0,0,0,1,1,1,1,1};
int ans=0;
void dfs(int g[][4],int i,int j){//连通检查 g[i][j]=0;if(i-1>=0&&g[i-1][j]==1) dfs(g,i-1,j);if(i+1<3&&g[i+1][j]==1)  dfs(g,i+1,j);if(j-1>=0&&g[i][j-1]==1) dfs(g,i,j-1);if(j+1<4&&g[i][j+1]==1)  dfs(g,i,j+1);
}
bool check(int a[12]){int g[3][4];for(int i=0;i<3;i++)for(int j=0;j<4;j++){if(a[i*4+j]==1) g[i][j]=1;else            g[i][j]=0;}int cnt=0;//连通块数 for(int i=0;i<3;i++){for(int j=0;j<4;j++){if(g[i][j]){dfs(g,i,j);cnt++;}}} if(cnt==1) return true;else       return false;
}
int main()
{do{if(check(a)) ans++;}while(next_permutation(a,a+12));cout<<ans<<endl;return 0;
}

第八题
题目：四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法
程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入：
5
则程序应该输出：
0 0 1 2再例如，输入：
12
则程序应该输出：
0 2 2 2再例如，输入：
773535
则程序应该输出：
1 1 267 838

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。

思路1：
通过分析：a<=sqrt(n/4)+1，b<=sqrt(n/3)+1，c<=sqrt(n/2)+1，d<=sqrt(n)+1。
在枚举出a,b,c,d，满足条件就输出（见代码8-1）。思路简单，但是在n最大时，时间复杂度为10^12，会超时，这是实在无思路的办法，可以得部分的分。
代码8-1：

#include<iostream>
#include<cmath>
using namespace std;int main()
{int a,b,c,d,n;cin>>n;for(a=0;a<=sqrt(n/4)+1;a++){for(b=a;b<=sqrt(n/3)+1;b++)){for(c=b;c<=sqrt(n/2)+1;c++){for(d=c;d<=sqrt(n)+1;d++){if((a*a+b*b+c*c+d*d)==n){cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;return 0;}}}}}return 0; 
}

思路2：
在思路1上优化，就是分成两部分:a,b与c,d分别来处理。cd部分，求出cc+dd之和，并用map来记录平方之和对应c或d（这里本人用的是c），再用循环求出a与b，再来判断为c* c+d* d = = n-a* a-b* b（有利用判断也可以a* a-b* b+c* c+d* d = = n）， 再用map得出c,最后在求出d并输出。在分析时间复杂度最大为10^7，未超时。
代码8-2：

#include<iostream>
#include<cmath>
#include<map>
using namespace std;int n;
map<int,int>cache;
int main()
{cin>>n;for(int c=0;c*c<=n/2;c++){//处理c、d,并记录其平方之和for(int d=c;c*c+d*d<=n;d++){if(cache.find(c*c+d*d)=&#d()){cache[c*c+d*d]=c;}}}for(int a=0;a*a<=n/4;a++){//ab部分，并加以判断for(int b=a;a*a+b*b<=n/2;b++){if(cache.find(n-a*a-b*b)!&#d()){int c=cache[n-a*a-b*b];int d=(int)sqrt(n-a*a-b*b-c*c);cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;return 0; }}}  return 0; 
}

第九题
题目：交换瓶子
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：
2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。

输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。例如，输入：
5
3 1 2 5 4程序应该输出：
3再例如，输入：
5
5 4 3 2 1程序应该输出：
2

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。

思路：
通过读题就是把第i个位子放成i，就不断地交换就行了,并记录交换次数。其时间复杂度最大为10^4，未超时。
代码9：

#include<iostream>
using namespace std;int N=10001;
int n,ans=0;
int main()
{ cin>>n;int a[n+1];for(int i=1;i<=n ;i++) {cin>>a[i];}for(int i=1;i<=n ;i++) {if(a[i]==i) continue;else{int t = a[a[i]];a[a[i]]=a[i];a[i]=t;ans ++;}}cout<<ans<<endl;return 0;    
}

第十题
题目：最大比例
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数测试数据保证了输入格式正确，并且最大比例是存在的。例如，输入：
3
1250 200 32程序应该输出：
25/4再例如，输入：
4
3125 32 32 200程序应该输出：
5/2再例如，输入：
3
549755813888 524288 2程序应该输出：
4/1

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。

思路：
先让n个数据排序，再让他们前后两两相比得到n-1个比值，在对它们求能开的方数，得到一个数是公比。
代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std; typedef long long ll;
int N;
ll data[101];
ll gcd(ll a,ll b){ if(b==0) return a;return gcd(b,a%b);
}
struct R{ll x;ll y;R(ll _x,ll _y):x(_x),y(_y){ll g=gcd(x,y);x/=g;y/=g;}
}; 
vector<R> ratios;
map<ll,map<ll,ll> >all_ex;//all_ex[x][pow]==x开pow次方 
map<ll,map<ll,ll> >all_log;//all_log[x][y]==log_y_x，y的多少次方是x
void init(){for(int i=2;i<1e6;i++){ll cur=(ll)i*i;int pow=2;while(cur<1e12){all_ex[cur][pow]=i;all_log[cur][i]=pow;pow++;cur*=i;} } 
} 
ll extract(ll x,ll pow){if(pow==1) return x;if(x==1)   return 1;if(all_ex[x].find(pow)!=all_ex[x].end())//意味着x可以开pow次方 return all_ex[x][pow];elsereturn -1;
}
ll log(ll base,ll x){if(base==x) return 1;if(all_log[x].find(base)!=all_log[x].end())//意味着x可以的一个k,base的k次方是x return all_log[x][base];elsereturn -1;
}
int main()
{init();cin>>N; //输入 for(int i=0;i<N;i++) {cin>>data[i];}sort(data,data+N); //排序 if(N==2){ //处理亮相的特殊情况 R ans=R(data[1],data[0]);//cout<<ans.x<<"/"<<ans.y<<endl;return 0;}//两两比值以分数的形式储存在vector中 for(int j=0;j<N-1;j++){if(data[j+1]!=data[j]) //去重 ratios.push_back(R(data[j=1],data[j]));} //对第一个比值开1~pow（极限是40）次方，作为基数，如果这个基数是其他比值的基数，该基数就是答案 for(int pow=1;pow<=40;pow++){R ra0=ratios[0];ll x=ra0.x;ll y=ra0.y; cout<<x<<" "<<y<<endl; ll base_x=extract(x,pow); //对x开pow次方 ,作为基数去尝试 ll base_y=extract(y,pow);//对y开pow次方,作为基数去尝试 cout<<base_x<<" "<<base_y<<endl;if(base_x==-1 || base_y==-1) continue; //开不出来，就continue //能开，就去确认所有比值的base_x,base_y的整数次方//计log_x=log(xx,fx), log_y=log(yy,fy)要求必须是整数，且log_x==log_ybool all_macth=true;for(int i=1;i<ratios.size();i++) {ll xx=ratios[i].x;ll yy=ratios[i].y;ll log_x=log(base_x,xx);ll log_y=log(base_y,yy);if(base_y==1&&yy==1)  log_y=log_x;if(log_x==-1 || log_y==-1 || log_x!=log_y){all_macth=false;break;}cout<<xx<<" "<<yy<<endl;cout<<log_x<<" "<<log_y<<endl;}if(all_macth){R ans=R(base_x,base_y);cout<<ans.x<<"/"<<ans.y<<endl;return 0; }} return 0;
}