2020.1.4大一寒假训练五（GCD&&快速幂）
程序员文章站
2024-03-20 21:06:10
...
首先介绍一下一个无敌好用的IDE——vs code，这位布莱克精心编写了教程，感谢感谢，附上链接传送门。
Problem:A 最大公约数和最小公倍数（NEFU OJ 1077）
模板题。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int a,b;
while(cin >> a >> b)
{
int ans;
ans=__gcd(a,b); //内置gcd真香
cout << ans << " " << a/ans*b << endl;
}
return 0;
}Problem:B 又见GCD（NEFU OJ 992）
核心思路：暴力，b是gcd，且b!=c，c一定大于b。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
int a,b;
while(cin >> a >> b)
{
for(int i=b+1;;i++)
{
if(__gcd(i,a)==b)
{
cout << i << endl;
break;
}
}
}
return 0;
}Problem:C 多个数的最大公约数（NEFU OJ 764）
核心思路：两个两个数进行gcd，并把上一组的结果与下一个数gcd。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
LL a[15],n;
while(cin >> n)
{
LL ans;
for(int i=1;i<=n;i++)
cin >> a[i];
ans=__gcd(a[1],a[2]);
for(int i=3;i<=n;i++)
ans=__gcd(ans,a[i]);
cout << ans << endl;
}
return 0;
}Problem:D 多个数的最小公倍数（NEFU OJ 765）
核心思路：同ProbleC，求lcm(a,b)=a/gcd(a,b)*b,可以避免爆数值。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
LL a[15],n;
while(cin >> n)
{
LL ans;
for(int i=1;i<=n;i++)
cin >> a[i];
ans=a[1]/__gcd(a[1],a[2])*a[2];
for(int i=3;i<=n;i++)
ans=ans/__gcd(ans,a[i])*a[i];
cout << ans << endl;
}
return 0;
}Problem:E LCM&GCD（NEFU OJ 1411）
核心思路：暴力，（我同学写了一个跑了7ms，我写的500ms，后续我会再想想QAQ！！），本来我也以为暴力会超时，一直往gcd，lcm交并集想，然后wa了，后续我会继续验证。
我的暴力思路：利用性质从a到b循环，并添加判断条件。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(0);
int t;
while(cin >> t)
{
LL x,y;
while(t--)
{
cin >> x >> y;
LL ans=0,tmp,tmp2;
tmp=x*y; //lcm*gcd的性质
for(LL i=x; i<=y; i++)
{
if(tmp%i==0) //判定是否能整除
{
tmp2=__gcd(i,tmp/i);
if(tmp2==x&&tmp/i<=y)//二次判断，是否符合gcd==x，lcm不用进行判断，因为tmp是x*y的乘积，可以自己去带入lcm的公式验证一下
ans++;
}
}
cout << ans << endl;
}
}
return 0;
}Problem:F 人见人爱gcd（NEFU OJ 1221）（但是我真的是一点也不爱他呀QAQ！！）
核心思路：数学推导，如下图可见。
#include<bits/stdc++.h>
using namespace std;
int t, a, b;
int main()
{
ios::sync_with_stdio(0);
while(scanf("%d", &t) != EOF)
{
while(t--)
{
scanf("%d%d", &a, &b);
printf("%d\n", a*a-2*__gcd(a, b)*b);
}
}
return 0;
}Problem:G 高木同学的因子（NEFU OJ 1669）
核心思路：因子分解，具体事项在代码的注释中。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL a,b;
while(~scanf("%lld%lld",&a,&b))
{
LL sum=0;
int ans=__gcd(a,b); //计算他是因为gcd是取a，b的公共因子的
for(int i=1;i*i<=ans;i++) //计算一半就行
if(ans%i==0)
sum++;
if(sqrt(ans)*sqrt(ans)==ans) //中间的因子是不是sqrt()为整数
printf("%lld\n",2*sum-1); //若是整数，×2就会多计算一次,例子在代码的最后面
else
printf("%lld\n",2*sum);
}
return 0;
}
//比如16 32的公共因子={1,2,4,8,16},sqrt(gcd(16,32))==4,他只能算一次，不能重复计算。Problem:H 快速幂取模（NEFU OJ 601）
核心思路：模板题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL fastPow(LL a,LL n,LL c)
{
LL base=a;
LL res=1;
const LL mod=c;
while(n)
{
if(n&1)
res=(res*base)%mod;
base=(base*base)%mod;
n>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
LL a,b,c;
while(cin>> a >> b >> c)
{
LL ans;
ans=fastPow(a,b,c);
cout << ans << endl;
}
return 0;
}Problem:I 库特的数学题（NEFU OJ 1666）
核心思路：可以自己先暴力写一下，并打出几个连续的答案，自己就能找到规律。
先说说我是怎么想到的：题干中1<=n<=1e18，你要是写递推，显然数组不能开到1e18，所以你就要找规律。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL M=1e9+7;
LL fastPow(LL a,LL n) //快速幂取模的模板
{
LL base=a;
LL res=1;
const LL mod=M;
while(n)
{
if(n&1)
res=(res*base)%mod;
base=(base*base)%mod;
n>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
LL n;
while(cin >> n)
{
LL ans;
ans=fastPow(3,n);
cout << (2*ans)%M << endl;//别忘了再一次取模
}
return 0;
}Problem:J 异或方程解的个数（NEFU OJ 1834）
这道题本来是ljw巨佬出来卡我们AK的，兴安家族让他失望了，QAQ。
核心思路：中午跟同学吃饭突发奇想想到的，我后续会证明一下，并更新。
一个蒟蒻写的证明，不知道对不对，不对的话请指正。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int fastPow(int a,int n)
{
int base=a;
int res=1;
while(n)
{
if(n&1)
res*=base;
base*=base;
n>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
LL n;
while(cin >> n)
{
int sum=0,ans;
while(n)
{
if(n&1)
sum++;
n>>=1;
}
ans=fastPow(2,sum);
cout << ans << endl;
}
return 0;
}