基础数论

目录Link：

有关质数问题

有关约数问题

同余与逆元

高斯解线性方程组

组合数学

博弈论

有关质数问题：

试除法判断质数：

bool isprime(int x)
{
	for(int i = 2; i <= x / i ; i++)
	{
		if(x % i == 0) return false;
	}
	return true;
}

筛质数的方法（线性筛法）：

int primes[N] , cnt;
bool st[N];
void get_primes(int n)
{
	for(int i = 2; i <= n; i++)
	{
		if(!st[i]) primes[cnt++] = i;
		for(int j = 0; primes[j] <= n / i; j++)
		{
			st[primes[j] * i] = true;
			if(i % primes[j] == 0) break;//如果这个数是质因数的话，则直接就可以break了
		}
	}
}

有关约数问题

int a[100010];
int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		int m;
		int cnt = 0;
		cin >> m;
		for(int i = 1; i <= m / i; i++)
		{
			if(i * i == m)
			{
				a[++cnt] = i;
				break;
			}
			if(m % i == 0)
			{
				a[++cnt] = i;
				a[++cnt] = m / i;
			}
		}
		sort(a + 1, a + cnt + 1);
		for(int i = 1 ; i <= cnt ; i++)
			cout << a[i] << endl;
		cout << endl;
	}
	return 0;
}

有关约数乘积————一个结论：

给出问题：求k个数乘积的约数个数

const int MOD = 1e9 + 7;
int main()
{
	int n,x;
	unordered_map<int , int> has;
	cin >> n;
	while(n--)
	{
		cin >> x;
		for(int i = 2 ; i <= x / i ; i++)
		{
			while(x % i == 0)//注意这是一个循环
			{
				x /= i;
				has[i]++;
			}
		}
		if(x > 1) has[x]++;
	}
	long long ans = 1;
	for(auto i : has) ans = ans * (i.second + 1) & MOD;
	cout << ans << endl;
	return 0;
}

有关约数之和，铭记结论：

给出问题：
给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。

const long long mod = 1e9 + 7;
int main()
{
	int n;
	cin >> n;
	unordered_map<int , int> p;
	while(n--)
	{
		int x;
		cin >> x;
		for(int i = 2; i <= x; i++)
		{
			while(x % i == 0)
			{
				x /= i;
				p[i]++;
			}
		}
		if(x > 1) p[x]++;
	}
	long long ans = 1;
	for(auto i : p)
	{
		long long t = 1;
		long long a = i.first , b = i.second;
		while(b--) t = (t * a + 1) % mod;
		ans = ans * t % mod;
	}
	cout << ans << endl;
	return 0;
}

最大公约数算法（欧几里得算法）

int gcd(int a , int b)
{
	return b ? gcd(b , a % b) : a;
}

有关欧拉公式

对于正整数n,欧拉函数是小于或者等于n的正整数钟与n互质的数的数目
给出问题
https://www.acwing.com/activity/content/problem/content/942/

signed main()
{
	int t; cin >> t;
	while(t--)
	{
		int n; cin >> n;
		int res = n;
		for(int i = 2; i <= n / i; i++)
		{
			if(n % i == 0) res = res * (i - 1) / i;
			while(n % i == 0) n /= i;
		}
		if( n > 1 ) res = res / n * (n - 1);
	`	cout << res << endl;
	}
	return 0;
}

有关博弈论基础

1.Nim游戏与ICG函数
取石子游戏：根据异或的知识可以知道，只要将所有组的石子个数进行异或，如果最后的结果得到的是1，则说明先手必赢。
a1^a2^a2…^an = x;
全局变量如果再函数内被重复定义了的话，会在该函数变成局部变量，其它函数的对该全局变量的关键字进行的操作则是对全局变量进行操作，不会收到被定义为局部变量的函数所影响
2.SG函数