22蓝桥杯训练4
题目一：最大公约数与最小公倍数
Description:
请计算两个整数值的最大公约数值及其最小公倍数值。（求最大公约数值时可采用辗转相除法这一方法，则可得到该值；而求取最小公倍数值则等于这两个整数值乘积与最大公约数值之比）
Input:
输入数据有多组，每组2个正整数a,b(2<a,b<1000)
Output:
在一行内输出a和b的最大公约数和最小公倍数；
Sample input:
15 10
Sample output:
5 30
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
int x,y,maxn=0,minx=0;
while(cin>>x>>y)
{maxn=gcd(x,y);
minx=(x*y)/maxn;
cout<<maxn<<" "<<minx<<endl;;
}
return 0;
}
cpp
题目二：又见GCD
Description:
设三个正整数a、b、c满足0 < a、b、c < 10^6，并且且c≠b。已知a与c的最大公约数为b，则当给定a与b的值时，请找出满足上述条件的最小正整数c。
Input:
每行输入两个正整数a,b。
Output:
输出对应的c，每组测试数据占一行
Sample input:
6 2
12 4
Sample output:
4
8
#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
if(y==0) return x;
return gcd(y,x%y);
}
int main()
{
long long a,b,c,i;
while(cin>>a>>b){
for(i=b;1;i++){
if(gcd(i,a)==b&&i!=b){
break;
}
}
cout<<i<<endl;
}
return 0;
}
cpp
题目三：多个数的最大公约数
Description:
输入n（其中n≤10）个正整数，并计算这些整数的最大公约数值。注意所有数据的取值范围均不超过long long类型所能表示的范围。
Input:
输入的数据包含多组，在第一行为数字n的情况下，在第二行中包含n个正整数，并且每一组占据两行
Output:
输出一个数，即这n个数的最大公约数。
Sample input:
5
2 4 6 8 10
2
13 26
Sample output:
2
13
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int ngcd(int *ar,int n)
{
if(n==1) return ar[n];
return gcd(ar[n],ngcd(ar,n-1));
}
int main()
{
int n,ar[10];
int maxn;
while(cin>>n)
{for(int i=1;i<=n;i++)
cin>>ar[i];
maxn=ngcd(ar,n);
cout<<maxn<<endl;}
return 0;
}
cpp
题目四：多个数的最小公倍数
Description:
指定不超过10的正整数集合，请计算出这些数字的最小公倍数值，并确保所有运算结果均不超过long long类型的最大值
Input:
输入数据有多批次,每个批次两行.第一行为n个数字表示要输入的数量;第二行为具体的n个正整数值.
Output:
输出一个数，即这n个数的最小公倍数。
Sample input:
5
2 4 6 8 10
2
13 26
Sample output:
120
26
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int nlcm(int *ar,int n)
{
if(n==1) return ar[n];
return lcm(ar[n],nlcm(ar,n-1));
}
int main()
{
int n,ar[10];
int minx;
while(cin>>n)
{for(int i=1;i<=n;i++)
cin>>ar[i];
minx=nlcm(ar,n);
cout<<minx<<endl;}
return 0;
}
cpp
题目五：LCM&GCD
Description:
JWGG近期完全沉浸在他的研究领域。他正致力于深入探讨这两个核心概念——最小公倍数与最大公约数。与此同时，在另一个同样热爱的研究领域里有另一位同行——YZMM——她同样在这两个数学问题上有着深厚的造诣。YZMM decided to challenge JWGG with a math problem: within the interval [x, y], determine the number of integer pairs that satisfy the condition where their greatest common divisor is x and their least common multiple is y. Kindly note that x and y can be as large as 1e12, which adds a layer of complexity to this problem for JWGG. Clever readers are encouraged to provide a solution.
Input:
在第一行处输入一个整数T（其中T≤100），表明共有T组数据。随后每一组将包含两个数值x和y（其中满足条件的数值范围为：1 \leq x \leq y \leq 1 \times 10^{12}）。问题定义见题目描述。
Output:
输出一行表示答案。
Sample input:
1
2 12
Sample output:
4
#include <bits/stdc++.h>
using namespace std;
int gcd1(int a,int b)
{
if(b==0) return a;
return gcd1(b,a%b);
}
int main()
{
int T;
while(cin >> T)
{
while(T--)
{
long long gcd,lcm,c;
cin >> gcd >> lcm;
c=gcd*lcm;
long long i,num=0;
for(i=gcd; i<=lcm; i+=gcd)
{
if(c%i==0&&gcd1(i,c/i)==gcd)
num++;
}
cout << num << endl ;
}
}
return 0;
}
cpp
题目六：人见人爱gcd
Description:
x+y=a,lcm(x,y)=b;已知a和b求解x2+y2
Input:
多组数据输入。
第一行一个t表示a,b数对的数量。
接下来t行2个数表示a,b
T<=100000 a,b<10^9;
Output:
每组样例输出t行每行一个数表示x2+y2;
Sample input:
2
6 4
6 3
Sample output:
20
18
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
long long t,a,b;
double ans;
while(cin>>t){
while(t--){
cin>>a>>b;
ans=a*a-2*gcd(a,b)*b;
cout << fixed << setprecision(0) << ans << endl;
}
}
return 0;
}
cpp
题目七：高木同学的因子
Description:
今日西片同学又一次遭到了高木同学的捉弄。高木同学与西片同学进行了一场游戏：两人各自在心中默想了一个数字，并将此数字分别标记为x和y（其中1≤x,y≤1018）。接着要求西片同学计算有多少个整数同时是x和y的因数。因为西片与高木拥有良好的配合默契性，在此游戏中所选择的两个数字x和y的最大公约数不会超过109。面对这一问题时，请你能否帮助西片理解并解答这个问题呢？
Input:
单组输入 数据占一行，包含两个整数x和y（1<=x,y<=1e18），保证gcd（x,y）<=1e9。
Output:
输出既是x因子又是y因子的整数的个数。输出占一行
Sample input:
12 36
Sample output:
6
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
long long i,x,y,num=0,sum;
cin>>x>>y;
sum=gcd(x,y);
for(i=1;i*i<sum;i++)
{
if(sum%i==0) num+=2;
}
if(i*i==sum) num++;
cout<<num<<endl;
return 0;
}
cpp
题目八：快速幂取模
Description:
给定A,B,C，计算AB%C，这里AB代表A的B次方
Input:
输入数据有多组，每组数据一行，有3个正整数分别为A,B和C，1<=A,B,C<=1000000000
Output:
输出A^B%C的值
Sample input:
2 3 5
8 2 10
Sample output:
3
4
#include <iostream>
using namespace std;
typedef long long ll;
ll modPow(ll a, ll b, ll c) {
ll result = 1;
a = a % c;
while (b > 0) {
if (b % 2 == 1) {
result = (result * a) % c;
}
a = (a * a) % c;
b = b / 2;
}
return result;
}
int main() {
ll a, b, c;
while (cin >> a >> b >> c) {
cout << modPow(a, b, c) << endl;
}
return 0;
}
cpp
题目九：库特的数学题
Description:
库特对各种高难度数学题充满兴趣。某天，她翻开书本时遇到了一道难题。已知a₁=6,a₂=18,且当n≥3时有递推关系式aₙ=2aₙ₋₁+3aₙ₋₂（其中下标表示项的位置），对于给定的一个数字n，请计算出aₙ的值。（由于数值可能非常庞大，请将结果对1e9+7取模）
Input:
一个整数n（1<=n<=1e18）
Output:
a[n]对1e9+7取模后的答案
Sample input:
5
Sample output:
486
#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll solve(ll n) {
if (n == 1) {
return 6 % MOD;
} else if (n == 2) {
return 18 % MOD;
}
ll a = 6, b = 18, c;
for (ll i = 3; i <= n; i++) {
c = (2 * b + 3 * a) % MOD;
a = b;
b = c;
}
return c;
}
int main() {
ll n;
cin >> n;
cout << solve(n) << endl;
return 0;
}
cpp
题目十：异或方程解的个数
Description:
最近在给大一新生讲解课程时，自感水平有限。想着试着解一道有趣的题目来提升自己时，却遇到了一个看似简单的数学问题。这道题 intriguing 的地方在于它巧妙地结合了逻辑运算与代数求解。具体来说，在二进制运算中定义了一种特殊的运算符 ^ ，其特性与传统意义上的幂次运算不同。为了更好地理解这个问题的本质，在深入分析后发现可以通过构建特定条件下的递推关系来找到所有满足要求的变量组合数目
具体来说，在二进制运算中定义了一种特殊的运算符 ^ ，其特性与传统意义上的幂次运算不同。具体来说，在二进制运算中定义了一种特殊的运算符 ^ ，其特性与传统意义上的幂次运算不同
Input:
多组输入数据（不超过2000000组）
每组输入数据包含一个整数n，含义如题。
Output:
对于每组输入数据，你需要输出一个整数，表示解的个数。
Sample input:
0
2
Sample output:
1
2
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n,temp;
while(cin>>n){
temp=0;
for(int j=0;j<31;j++){
if(n&(1<<j)) temp++;
}
cout<<(1<<temp)<<endl;
}
return 0;
}
cpp
