计蒜客2019年蓝桥杯国赛B组模拟赛题题解

第一题

标题：标签

代码

import java.io.*; import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { long sum=1; for(int i=2;i<=1325476;i++) { sum=sum*i; while(sum==0) sum=sum/10; sum=sum0000000; } System.out.println(sum); } }

运行结果： 注意这里多保留了几位，最终结果为：137664

第二题

标题：101串

代码

第三题

标题：游戏

代码

import java.io.*; import java.math.*; import java.util.*; /* 可以观察到C+D=A+B=定值(Constant)，C永远小于Constant 第一轮：C=2*A=(2*A)%Constant 第二轮：C=(2*2*A)%Constant …… 第K轮：C=(2^K*a)%Constant D=Constant-C A=min(C,D) */ public class Main { public static void main(String[] args) { BigInteger A=new BigInteger("482333897982347239"); BigInteger B=new BigInteger("557432748293424892"); BigInteger K=new BigInteger("1389472389742429877"); BigInteger Constant=A.add(B); BigInteger C=BigInteger.valueOf(2).modPow(K, Constant).multiply(A).mod(Constant); System.out.println(C.min(Constant.subtract(C))); } }

结果：383513242709218605

第四题

标题：公约数

代码

import java.io.*; import java.util.*; /* 数组a和f分别存储输入数据和每个数出现的次数 maxn记录该组数中的最大值 从maxn开始找，从f数组中统计是maxn倍数的数出现的次数 如果出现的次数大于k则最大公约数即为maxn,否则继续向下寻找 */ public class Main { static int maxn=0,k; static int result=1; static int[] f; //判断是num的倍数的数出现的次数 static boolean judge(int num) { int sum_count=0; for(int i=num;i<=maxn;i+=num) { sum_count+=f[i]; } //如果出现次数大于k,则num就是最大公约数,返回true if(sum_count>=k) return true; return false; } public static void main(String[] args) throws IOException { BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); String[] s=reader.readLine().split(" "); int n=Integer.parseInt(s[0]); k=Integer.parseInt(s[1]); String[] ss=reader.readLine().split(" "); int[] a=new int[n];//存储输入的数 f=new int[1000001];//存储每个数出现的次数 for(int i=0;i<n;i++) { a[i]=Integer.parseInt(ss[i]); f[a[i]]++; maxn=Math.max(maxn,a[i]); } //从大到小判断每个数 for(int i=maxn;i>1;i--) { if(judge(i)&&f[i]!=0) { result=i; break; } } System.out.println(result); reader.close(); } }

第五题 代码

import java.io.*; import java.math.*; import java.util.*; public class Main { static int[] pre; public static void main(String[] args) throws IOException { BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); String[] s=reader.readLine().split(" "); int N=Integer.parseInt(s[0]); int M=Integer.parseInt(s[1]); pre=new int[100001]; //存放顶点 for(int i=1;i<=N;i++) pre[i]=i; int result=1; int mod=1046513837; for(int i=0;i<M;i++) { String[] s1=reader.readLine().split(" "); int u=Integer.parseInt(s1[0]); int v=Integer.parseInt(s1[1]); if(find(u)==find(v)) //引入u-v边会形成环 result=(result*2)%mod;//引入一条边会使环的数量变为原来的两倍 else//构不成环则连接 connect(u,v); System.out.println(result-1); } } private static void connect(int u, int v) { int fx=find(u); int fy=find(v); if(fx!=fy) pre[fx]=fy; } private static int find(int x) { if(pre[x]==x) return x; else return find(pre[x]); } }