2020年1月4日 OJ习题【gcd&lcm】+【快速幂取模】
程序员文章站
2024-01-01 17:46:16
...
最大公约数和最小公倍数
模板题！！！
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)//最大公约数//
{
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)//最小公倍数//
{
return a/gcd(a,b)*b;
}
int main()
{
int a,b,x,y;
while(cin>>a>>b)
{
x=gcd(a,b);
y=lcm(a,b);
cout<<x<<" "<<y<<endl;
}
return 0;
}
又见GCD
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int main()
{
int a,b,c;
while(cin>>a>>b)
{
for(int i=b+1;i>b;i++)//c必然大于b，因此让i从b+1开始依次找，符合条件的就是最小的c//
{
if(b==gcd(a,i))
{
c=i;
break;
}
}
cout<<c<<endl;
}
return 0;
}
多个数的最大公约数
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int main()
{
int n;
long long a,x[11];
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>x[i];
}
a=x[0];
for(int i=1;i<n;i++)
{
a=gcd(a,x[i]);
}
cout<<a<<endl;
}
return 0;
}
多个数的最小公倍数
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int main()
{
int n;
long long a,x[11];
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>x[i];
}
a=x[0];
for(int i=1;i<n;i++)
{
a=lcm(a,x[i]);
}
cout<<a<<endl;
}
return 0;
}
LCM&GCD
该题不需要双重循环，只需要让i进行循环，由gcd(a,b)lcm(a,b)=ab,可得出对应的j（必须是整除），然后再进行判断i，j是不是同时满足条件即可
但是由于数比较大，因此不能用int！！！
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
return a/gcd(a,b)*b;
}
int main()
{
int t,count;
long long i,j,x,y;
while(cin>>t)
{
for(int k=0;k<t;k++)
{
cin>>x>>y;
count=0;
for(i=x;i<=y;i+=x)//这里不用i++，每次都加x，能缩短时间//
{
if((x*y)%i==0)//如果能整除//
{
j=x*y/i;
if(gcd(i,j)==x&&lcm(i,j)==y)
count++;
}
}
cout<<count<<endl;
}
}
return 0;
}
人见人爱gcd
通过公式推导，可得出gcd(x,y)=gcd(a,b),然后就可以计算了
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int a,b,x;
int t;
while(cin>>t)
{
for(int k=0;k<t;k++)
{
scanf("%d%d",&a,&b);
x=a*a-2*b*gcd(a,b);
printf("%d\n",x);
}
}
return 0;
}
数比较大，因此直接用cin，cout会超时，可以用scanf和printf，或者加上这句
ios::sync_with_stdio(false);
高木同学的因子
求两个数的所有因子，相当于求两个数最大公约数的全部因子
为了不TLE，在找因子时，不能从头到尾去遍历，具体看代码
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
long long x,y,i,j;
int count;
count=0;
scanf("%lld%lld",&x,&y);
long long z=gcd(x,y);
i=1;
while(i<=z)
{
if(z%i==0)//如果z能被i整除，就说明商也一定是z的因子，因此计数器应+2//
{
count+=2;
j=z/i;
if(i==j)//但是i从小到大找，j必然从大到小变化，因此总会有i，j相遇的时候，情况有如下两种//
{
count--;//如果i=j，则上一步的+=2多加了1//
break;
}
if(i>j)
{
count-=2;//如果i<j,也就是说没有i=j的情况，则上一步的+=2都是多余的//
break;
}
}
i++;
}
printf("%d\n",count);
return 0;
}
快速幂取模
模板题！！！
#include <bits/stdc++.h>
using namespace std;
long long quickmod(long long a,long long b,long long c)
{
int ret=1;
while(b)
{
if(b&1) ret=ret*a%c;
a=a*a%c;
b>>=1;
}
return ret;
}
int main()
{
long long a,b,c,x;
while(cin>>a>>b>>c)
{
x=quickmod(a,b,c);
cout<<x<<endl;
}
return 0;
}
库特的数学题
找规律发现，每一位数十=是有规律的，每一位都是2*pow(2,n),因此，可以用快速幂取模来计算
#include <bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
long long quickmod(long long a,long long b)
{
long long r=1;
while(b)
{
if(b&1) r=r*a%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
int main()
{
long long n,x;
while(cin>>n)
{
x=quickmod(3,n);
x*=2%mod;
x%=mod;
cout<<x<<endl;
}
return 0;
}
异或方程解的个数
先移项：n=x+(n^x)，然后看二进制数的某一位，讨论即可发现规律：
n x+(n^x)
1 0+(1^0)==1
1 1+(1^1)==1
0 0+(0^0)==0
0 1+(0^1)==10
可以发现，第四种情况(n=0,x=1)会改变产生进位，改变了n的值，所以排除第四种情况。
综合第三，四种情况，可以发现，如果n的某一位为0的话，那么x对应位只能为0。
再来看第一，第二种情况，我们发现，当n的某一位为1时，x的对应位可以为1，可以为0。
所以，我们只需求出n的二进制数中，有多少个1即可,假设有y个1，答案就是2^y.
即把整个方程转化成二进制去看，看每一位是否能对应上，通过上述讨论不难发现，当n的某一二进制位为0时，对应的x的二进制位只能是0，即只有一种情况(*1)，当n的某一二进制位是1时，对用的x的二进制位可以为0，1，即有两种情况(*2)，因此，计算出x的二进制每一位符合条件的所有情况就是答案！！！
#include <bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
long long quickmod(long long a,long long b)
{
long long r=1;
while(b)
{
if(b&1) r=r*a;
a=a*a;
b>>=1;
}
return r;
}
int main()
{
long long n,x,count;
ios::sync_with_stdio(false);
while(cin>>n)
{
count=0;
while(n)
{
if(n&1)//看n的每一个二进制位是不是1//
count++;
n>>=1;
}
x=quickmod(2,count);
cout<<x<<endl;
}
return 0;
}