1.进制转换问题
2.数论板块
模运算
快速幂
GCD和LCM
扩展欧几里得算法与二元一次方程的整数解
同余和逆元
素数
3.洛谷题解（贪心，DP，搜索）
进制转换问题
P1143 进制转换
先有n进制数转化为十进制，再由十进制转化为m进制
1.字符转化为数字
2.数字转化为字符
3.本体最大的一个坑。转化为m进制的输出格式是有顺序的！！先转化的在后面
int change(char ch)
{
return int(ch-'0'); //字符转化为数字
}
char ch1(int ch)
{
return char(ch+'0');
}
int main()
{
int n;cin>>n;
string s;cin>>s;
int m;cin>>m;
int ans=0,k=1;
for(int i=s.length()-1;i>=0;i--)
{
ans+=change(s[i])*k;
k*=n;
}
string tmp="";
while(ans)
{
tmp=ch1(ans%m)+tmp; //本体最大的坑，不能写成 tmp+=ch1(ans%m); 顺序错误
ans/=m;
}
cout<
P1604 B进制星球
（主要用到高精度计算，进位问题，关键在与逆序存储字符串，输出顺序，和转化问题）
1.现将给定的两个字符串存到整型数组中
2.在进行高精度加减操作
3.去除前导0
4.输出再从后往前输出
代码思路写的还是很清晰的
int num1[2005],num2[2005],num[2005];
char s1[2005],s2[2005];
int main()
{
int B;cin>>B;
cin>>s1>>s2;
int k1=strlen(s1),k2=strlen(s2);
for(int i=0;i='A')
num1[k1-i]=s1[i]-'A'+10; //字符串逆序存储到数组当中
else
num1[k1-i]=s1[i]-'0'; //解决高位进1的问题
}
for(int i=0;i='A')
num2[k2-i]=s2[i]-'A'+10;
else
num2[k2-i]=s2[i]-'0';
}
int k=0,b=0;
while(k<=k1||k<=k2)
{
k++;
num[k]=num1[k]+num2[k]+b;
b=num[k]/B;num[k]%=B;
}
while(num[k]==0&&k>1) k--;
for(int i=k;i>=1;i--)
{
if(num[i]<10) cout<
模运算
除法的取模需要用到逆元
(a+b) mod m=((a mod m)+(b mod m)) mod m
(a-b) mod m=((a mod m)-(b mod m)) mod m
(a*b) mod m=((a mod m)*(b mod m)) mod m
P7521 [省选联考 2021 B 卷] 取模
看到个不太正规的做法。为了求最大的取模得到的数，盲猜是肯是从最大的几个数中选取，于是对于最大的几个数进行遍历，当遍历到最后6个的时候，便可以AC。
sort(a+1,a+1+n);
for(int k=n-5;k<=n;k++)
{
for(int i=n-5;i<=n;i++)
{
if(i==k) continue;
for(int j=i+1;j<=n;++j)
{
if(j==k) continue;
ans=max(ans,(a[i]+a[j])%a[k]);
}
}
}
cout<
快速幂
分治法实现
int fastpow(int a,int n)
{
if(n==1) return a;
int tmp=fastpow(a,n/2);
if(n%2==1)
return tmp*tmp*a;
else
return tmp*tmp;
}
int main()
{
int a,n;
cin>>a>>n;
cout<
采用位运算实现快速幂
int fastpow(int a,int n)
{
if(n==1) return a;
int tmp=fastpow(a,n/2);
if(n%2==1)
return tmp*tmp*a;
else
return tmp*tmp;
快速幂取模：
a的n次方 mod m =(a mod m)的n次方 mod m ;
矩阵快速幂模板
HDU 2817
#include
using namespace std;
const int maxn=2;
const int mod=1e4;
struct matrix
{
int m[maxn][maxn];
matrix()
{
memset(m,0,sizeof(m)); //对于矩阵初始化
}
};
matrix mul(matrix a,matrix b)
{
matrix c;
for(int i=0;i>=1;
}
return tmp;
}
int main()
{
matrix a1;
for(int i=0;i>a1.m[i][j];
int n;
cin>>n;
matrix a2=fastpow(a1,n);
for(int i=0;i
GCD和LCM
GCD（最大公约数）: return b==0 ? a:gcd(b,a%b);
LCM ( 最小公倍数 ) : return a/ gcd(a,b)*b;
P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
（需要注意的是：如果最大公约数和最小公倍数是同一个数，也就是两个数相等的情况下，就一组）
#include
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 x,y;
cin>>x>>y;
int num=x*y;
int ans=gcd(x,y); //最小公约数
int cot=lcm(x,y); //最大公倍数
int p=0;
if(x!=ans)
cout<<0<
扩展欧几里得算法和二元一次方程的整数解
