博客最后修改时间：2025年8月7日 15:02 以此证明我还活着

---

#J31401. 试除法判定质数

思路：

题目要求判断$a_i$是否是质数，其实可以从$2$开始，一个一个的去试除，如果有能整除的，就说明$a_i$不是质数，因为$a_i$可以被某个数整除，另外如果$a_i<2$，说明$a_i$不是质数。代码如下：

// 此处ai用a代替
bool zs (int a)
{
  if (a < 2) return false; // a<2，a不是质数，返回false
  for (int i = 2; i <= a; i++)
  {
    if (a % i == 0) return false; // a可以被i整除，a不是质数，返回false
  }
  // a是质数，返回true
  return true;
}

但是，以上代码的时间复杂度为$O(n)$，当数据太大时，会有超时的风险。

那咋办？

其实，$i$只用到$\sqrt{a}$就可以了。因为，如果$a\!\!\mod i = 0$，那么，$i$和$\frac{a}{i}$中间一定有一个数是$\leq\sqrt{a}$的。这样，$O(n)$的时间复杂度就降到了$O(\sqrt{n})$。 代码如下：

bool zs (int a)
{
  if (a < 2) return false; // a<2，a不是质数，返回false
  for (int i = 2; i <= sqrt(a); i++)
  {
    if (a % i == 0) return false; // a可以被i整除，a不是质数，返回false
  }
  // a是质数，返回true
  return true;
}

完整代码：

#include <bits/stdc++.h>
using namespace std;

int n;

bool zs (int a)
{
	if (a < 2) return false;
	for (int i = 2; i <= sqrt(a); i++)
	{
		if (a % i == 0) return false;
	}
	return true;
}

int main ()
{
	cin >> n;
	while (n--)
	{
		int a;
		cin >> a;
		if (zs(a)) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;	
}

---

#J31402. 分解质因数

思路：

(这里$a_i$我给换成$a$了) 这道题和上一道题的核心一样，都是一个一个的去试除，但是，这道题在试除的时候，不用去判断$i$是否为质数，因为假设当前枚举的数$i$是合数，那么前面必然已经枚举过$i$的质因子了，所以在前面已经通过不断的除使得质因子无法整除 $a$了，既然质因子都无法整除，作为合数的$i$必然也不可能整除，所以合数$i$并不会影响程序的结果，也就不需要去判断质数合数。

代码：

#include <bits/stdc++.h>
using namespace std;

long long n, a;

int main ()
{
  // 这里把n和a互换了一下
	cin >> a;
	while (a--)
	{
		cin >> n;
		bool t = true;
		for (long long i = 2; i <= sqrt(n); i++)
		{
			int x = 0;
			if (n % i == 0)
			{
				cout << i << ' ';
				while (n % i == 0)
				{
					x++;
					n /= i;
				}
				cout << x << endl;
			}
		}
		if (n != 1) cout << n << ' ' << 1 << endl;
	}
	return 0;
}

---

#J31403. 筛质数

思路：

刚才说过判断质数的方法，但是，$O(\sqrt{n})$的时间复杂度对于这道题来说还是太慢了点。

那咋办？

首先，一个数的倍数一定是合数，这也是质数筛的核心思想。咱们可以定义一个数组，名为$a$，先把$a_0$和$a_1$都设为$1$，然后遍历这个数组。如果$a_i=0$，那么就把$i$的倍数位置全部设为$1$，顺便再加一个变量，来统计质数个数。遍历完后，$a$数组中所有值为$0$的下标就是质数。代码如下：

void g (int n) 
{
  a[0] = a[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (!a[i]) ans++; // ans为计数变量
		for (int j = i + i; j <= n; j += i) a[j] = 1;
	}
}

完整代码：

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1e6 + 5;
int ans = 0;
bool s[N];

void g (int n) 
{
	for (int i = 2; i <= n; i++) 
	{
		if (!s[i]) ans++;
		for (int j = i + i; j <= n; j += i) s[j] = 1;
	}
}

int main ()
{
	cin >> n;
	g(n);
	cout << ans;
	return 0;
}

---

#J31404. 试除法求约数

思路：

这一次还是一样，从$1$试到$\sqrt{a_i}$，有$a_i$能整除的数就把这个数和$\frac{a_i}{\sf{这个数}}$给存进数组里，完事之后排个序再输出就完了。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, a;
vector<int> ans;

int main ()
{
	cin >> n;
	while (n--)
	{
		cin >> a;
		ans.clear();
		for (int i = 1; i * i <= a; i++)
		{
			if (a % i == 0)
			{
				ans.push_back(a / i);
				ans.push_back(i);
			}
		}
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
		cout << "\n";
	}
	return 0;
}

---

#J31405. 约数个数

思路：

一个数的因数个数可以通过其质因数分解来确定。具体来说，如果一个数$n$可以被分解为质因数的乘积，即$n=\prod_{i=1}^{k} p_i^{x_i}$，那么那么$n$的因数个数$r$可以通过以下公式计算：

$$\prod_{i=1}^{k}\left(x_i+1\right)$$

例如，$200$可以被分解为$2^3\times5^2$，那么$200$的因数个数为：

$$(3+1)\times(2+1)=12$$

那我们只需要对每个$a_i$进行质因数分解，统计所有质因子的指数，然后求和即可，因为数字范围比较大，所以可以使用unordered_map来记录每个质因子的出现次数。

代码：

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int s = 1e9 + 7;
unordered_map<int, int> mp;
int n, a;
ll ans = 1;

int main () 
{
	cin >> n;
	for (int i = 1; i <= n; i++) 
	{
		cin >> a;
		for (int i = 2; i <= a / i; i++)
		{
			while (a % i == 0) 
			{
				a /= i;
				mp[i]++;
			}
		}
		if (a > 1) mp[a]++;
	}
	for (auto i : mp) ans = ans * (i.second + 1) % s;
	cout << ans;
	return 0;
}

---

#J31406. 约数之和

思路：

根据数学归纳法可得，当$n=\prod_{i=1}^{k}p_i^{x_i}$，其因数和为：

$$\prod_{i=1}^{k}\left(\sum_{j=0}^{x_i}p_i^{j}\right)$$

代码：

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int s = 1e9 + 7;
ll n, a, ans = 1;
unordered_map<ll, ll> mp;

int main ()
{
	cin >> n;
	while (n--)
	{
		cin >> a;
		for (int i = 2; i <= sqrt(a); i++)
		{
			while (a % i == 0)
			{
				a /= i;
				mp[i]++;	
			}	
		} 
		if (a > 1) mp[a]++;
	}
	for (auto i : mp)
	{
		ll sum = 1, a = i.first, b = i.second;
		while (b--)
		{
			sum = (sum * a + 1) % s;
		}
		ans = ans * sum % s;
	}
	cout << ans;
	return 0;
}

---

#J31407. 最大公约数

思路：

很容易想到，如果要求$a$和$b$的最大公因数，我们只需要把$min(a, b)\sim1$的数字列出来，然后找到第一个能同时整除$a$和$b$的数字，就是最大公因数了，代码如下：

int gcd(int a, int b) 
{
	for (int i = min(a, b); i >= 1; i--) 
    {
		if (a % i == 0 and b % i == 0) return i;
	}
}

显然，此代码的时间复杂度是$O(n)$级别的，有超时的风险。

那咋办？

还有一个求最大公因数的方法叫辗转相除法，代码如下：

int gcb (int a, int b)
{
	if (a % b == 0) return b;
	return gcb(b, a % b);
}

时间复杂度为${{O}(\log n)}$

完整代码：

#include  <bits/stdc++.h>
using namespace std;

int n, a, b;

int gcb (int a, int b)
{
	if (a % b == 0) return b;
	return gcb(b, a % b);
}

int main ()
{
	cin >> n;
	while (n--)
	{
		cin >> a >> b;
		cout << gcb(a, b) << "\n";
	}
	return 0;
}

---

#182. 快速幂

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll a, b, p;

ll q (ll a, ll b, ll p)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b = b >> 1;
	}
	return ans;
}

int main ()
{
	cin >> a >> b >> p;
	cout << q(a, b, p) << "\n";
	return 0;
}

---

#J31409. 64位整数乘法

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll a, b, p;

ll q (ll a, ll b, ll p)
{
	ll ans = 0;
	while (b)
	{
		if (b & 1) ans = (ans + a) % p;
		a = a * 2 % p;
		b = b >> 1;
	}
	return ans;
}

int main ()
{
	cin >> a >> b >> p;
	cout << q(a, b, p) << "\n";
	return 0;
}

---

$$\rm{\blue{1161041010101110100}}$$

$$\rm{\blue{the~~end}}$$