第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-660 Hankson 的趣味题

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-660 Hankson 的趣味题

前言

关于数学的疑问

算法训练 Hankson 的趣味题

C语言

C 语言

Java语言

总结

第六届——第十三届省赛题解

第六届——第十二届国赛题解

前言

这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。

关于数学的疑问

蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的

1、简单数学(基础运算) 2、位运算 3、线性代数 4、离散数学(组合数学) 5、初等数论(整数的性质) 6、概率论 7、几何

虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。

算法训练 Hankson 的趣味题

资源限制

内存限制：64.0MB C/C 时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

　　Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson 正在思考一个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x 满足： 1． x 和a0 的最大公约数是a1； 2． x 和b0 的最小公倍数是b1。 Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮助他编程求解这个问题。

输入格式

　　输入第一行为一个正整数n，表示有n 组输入数据。　　接下来的n 行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0 能被a1 整除，b1 能被b0 整除。

输出格式

　　输出共n 行。每组输入数据的输出结果占一行，为一个整数。　　对于每组数据：若不存在这样的 x，请输出0；若存在这样的 x，请输出满足条件的x 的个数；

样例输入

2 41 1 96 288 95 1 37 1776

样例输出

6 2

样例说明

　　第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。　　第二组输入数据，x 可以是48、1776，共有2 个。

数据规模和约定

　　对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。　　对于 100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000

题解：

C语言

代码语言：javascript复制

#include<stdio.h>
void jisuan( int , int , int , int , int * );
int gcd( int , int ); 
int main( void )
{
 int n ; 
 scanf("%d" , & n ) ; 
 while( n -- )
 {
  int a0 , a1, b0 , b1 ;
  int sum = 0 ; 
  scanf("%d%d%d%d" ,& a0 , & a1 , & b0 , & b1  );
  if( b1 % a1 == 0 )
  {
   jisuan( a0 , a1 , b0 , b1 , &sum );
  }
  printf("%dn", sum );
 }
 return 0 ; 
}
int gcd(int a, int b)
{
 if( b == 0 )
 {
  return a ; 
 }
 return gcd( b , a%b );
}
void jisuan( int a0, int a1, int b0, int b1, int * sum )
{
 int i , x ; 
 for( i = 1 ; i * i <= b1 ; i    )
 {
  if( b1 % i == 0 )
  {
   if(i % a1 == 0) 
   if(gcd( b1 / b0 , b1 / i ) == 1 && gcd( a0 / a1 , i / a1 ) == 1)
   {
       * sum ; 
   }
   int j = b1 / i ;
            if( j % a1 != 0 || i == j )
   {
    continue; 
   } 
   if( gcd( b1 / b0 ,  b1 / j  ) == 1 &&  gcd( a0 / a1 , j / a1 ) == 1)
   {
       * sum ; 
   }
  } 
 }
}

C 语言

代码语言：javascript复制

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long 
using namespace std;
const int N=45010;
const int inf=45000;
const int M=40000;
bool v[N];int prime[M],m;
inline void g_p()
{
	m=0;memset(v,false,sizeof(v));
	for(int i=2;i<=inf;i  )
	{
		if(!v[i])prime[  m]=i;
		for(int j=1;j<=m&&i*prime[j]<=inf;j  )
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int get(int &a,int b)
{
	int ans=0;
	while(a%b==0)a/=b,ans  ;
	return ans;
}
int a0,a1,b0,b1;
int calc(int x)
{
	int ans=0;
	int ma=get(a0,x),mb=get(b0,x),mc=get(a1,x),md=get(b1,x);
	if(ma==mc&&mb==md&&mc<=md)ans=md-mc 1;
	else if(ma>mc&&mb==md&&mc<=md)ans=1;
	else if(ma==mc&&mb<md&&mc<=md)ans=1;
	else if(ma>mc&&mb<md&&mc==md)ans=1;
	return ans;
	
}
int main()
{
	g_p();
	int n;scanf("%d",&n);
	while(n--)
	{
		int ans=1;
		scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
		for(int i=1;i<=m&&(ll)prime[i]*prime[i]<=b1;i  )
		{
			if(b1%prime[i]==0)
				ans*=calc(prime[i]);
		}
		if(b1>1)ans*=calc(b1);
		printf("%dn",ans);
	}
	return 0;
}

Java语言

在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。

代码语言：javascript复制

import java.util.Scanner;

public class Main {
    static int a,a1,b,b1;
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();
        while (n-->0){
            a=sc.nextInt();
            a1=sc.nextInt();
            b=sc.nextInt();
            b1=sc.nextInt();
            int ans=0,i;
            for(i=1;i*i<b1;i  ){
                if (b1%i!=0)
                    continue;
                if (judge(i)==true)
                    ans  ;
                if (judge(b1/i)==true)
                    ans  ;
            }
            if (i*i==b1)
                if (judge(i)==true)
                    ans  ;
            System.out.println(ans);
        }
    }
    public static int gcd(int x,int y){
        return y==0?x:gcd(y,x%y);
    }
    public static boolean judge(int i){
        if (i�!=0)
            return false;
        return gcd(a/a1,i/a1)==1&&gcd(b1/b,b1/i)==1;
    }
}

总结

没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第六届——第十三届省赛题解

所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。

第六届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123284163
第七届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123285783
第八届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123302677
第九届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123303285
第十届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123319090
第十一届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/123320205
第十二届Java省赛C组第一套	https://laoshifu.blog.csdn.net/article/details/123413141
第十二届Java省赛C组第二套	https://laoshifu.blog.csdn.net/article/details/123413271
第十三届Java省赛C组	https://laoshifu.blog.csdn.net/article/details/128891276

第六届——第十二届国赛题解

所有题目均有题解，部分第10题非最优解，至少跑20%数据

第六届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123440705
第七届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123442982
第八届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123443626
第九届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123443908
第十届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123444946
第十一届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123445601
第十二届Java国赛C组	https://laoshifu.blog.csdn.net/article/details/123446589

java https 网络安全数据结构 c语言

0 人点赞