1. 除法表达式（gcd法求最大公约数）
//给你一个除法表达式：X1/X2/X3/X4……/Xk
//通过添加括号，问能否得到整数
//分析可得，只有X2是不能做分子的。题目就转化为求一个分数能否为整数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int x[100];
int gcd(int a, int b)
{
return b==0 ? a : gcd(b,a%b); //gcd的递归层数不会超过4.75lgN + 1.6723，最大层数来自于gcd(Fn,Fn-1).其中Fn为斐波那契数列
}
int main ()
{
int i,j,k;
cin>>k;
for (i=1; i<=k; i++)
scanf("%d",x+i);
x[2]/=gcd(x[1],x[2]);
for (i=3; i<=k; i++)
x[2]/=gcd(x[2],x[i]);
if (x[2]==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
// gcd(a,b) * lcm(a,b) = a * b;
// 其中gcd(a,b)为最小公约数，lcm(a,b)为最大公倍数，
// 在求最大公倍数时，用 lcm(a,b) = a / gcd(a,b) * b 以免溢出
return 0;
}
2. 无平方因子的个数（素数筛选法的原理和应用）
//给出正整数n和m，区间[n,m]内的”无平方因子“的数有多少个？
//整数p无平方因子当且仅当不存在k>1,使得p是k^2 的倍数。1 <= n <= m <= 10^12, m - n <= 10^7
//
//素数筛选法：用vis[i]=1 来表示已经非素数
//memset(vis,0,sizeof(vis));
//for (int i = 2; i <= n; i++)
// if (!vis[i])
// for (j = i*2; j <= n; j+=i) vis[j]=1;
//这个代码的效率是O(nlogn)
//
//素数筛选法改进，并且用prime数组记录下素数
//
//int m = sqrt(n+0.5);
//int c = 0;
//memset(vis,0,sizeof(vist));
//for (int i = 2; i <= m; i++)
// if (!vis[i])
// {
// prime[c++]=i;
// for (j = i*i; j <= n; j+=i) vis[j]=1;
// }
//
//素数定理：π(x)~x/ln(x)
//
//
//那这道题也可以用类似的想法来解决，对于不超过sqrt(m)的所有素数p,筛选掉区间[n,m]内p^2 的所有倍数
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int vis[1000000],c=0;
int prime[100000];
void getprime(long long t)
{
int m = sqrt(t+0.5);
memset(vis,0,sizeof(vis));
for (int i=2; i<=m; i++)
if (!vis[i])
{
prime[c++]=i;
for (int j=i*i; j<=t; j+=i) vis[j]=1;
}
}
int map[11000000]={0};
int main ()
{
long long n,m,t;
cin>>n>>m;
t=sqrt(m+0.5);
getprime(t);
for (int i = 0; i < c; i++)
{
long long st,ed;
st = n / prime[i] / prime[i];
ed = m / prime[i] / prime[i];
for (long long j = st; j <= ed; j++)
{
long long tmp;
tmp = j * prime[i] * prime[i];
map[tmp-n] = 1;
}
}
int sum = 0;
for (int i = 0; i <= m-n; i++)
if (!map[i])
sum++;
cout<<sum<<endl;
}
3. 扩展欧几里得算法
//直线上的点
//求直线ax+by+c=0 上有多少个整点(x,y)满足x∈[x1,x2],y∈[y1,y2]。
//
//扩展欧几里得算法，找出一对整数(x,y),使得ax+by=gcd(a,b)
//递归实现： x1=y2; y1=x2-[a/b]*y2
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int x,y,d;
void ex_gcd(int a,int b)
{
if (!b)
{
x=1;
y=0;
return ;
}
ex_gcd(b,a%b);
int t = x;
x = y;
y = t - (a/b)*y;
}
void ex_gcd(int a, int b, int &d, int &x, int &y)
{
if (!b)
{
d=a;
x=1;
y=0;
}
else
{
ex_gcd(b,a%b,d,y,x);
y -= (a/b)*x;
}
}
int main ()
{
int a,b;
cin>>a>>b;
ex_gcd(a,b);
cout<<x<<" "<<y<<endl;
ex_gcd(a,b,d,x,y);
cout<<x<<" "<<y<<endl;
return 0;
}
其中x,y是ax+by=gcd(a,b)的一组解，(x+kb',y-ka')为任意解
若ax+by=c，其中c是gcd(a,b)的倍数，那么有整数解，否则无整数解