数论

Asdfre

2026-08-10 15:49:03

发布于：广东

20阅读

0回复

0点赞

（可能比较简洁，主要我自己看得懂，不懂得可以问我）

BSGS

求解 $a^x \equiv b$ $(mod$ $p)$ 的最小非负整数解 $x$ ， $(a,p)=1$

显然 $x$ 取值一定在 $[0,p-1]$ 间。

考虑分块，拆成 $m=\sqrt{q}+1$ 大小的块，使其覆盖全面，这样我们可以将 $x$ 表示为 $i \times m - j$ ，其中 $i \in [1,m]$ ， $j \in [0,m-1]$ 。

再回推式子：

$a^{i\times m -j} \equiv b$ $(mod$ $p)$

得到：

$(a^m)^i \equiv b \times a^j$ $(mod$ $p)$

我们可以用哈希表预处理出所有 $b\times a^j$ 的值，遍历 $i$ 查询有无在模 $p$ 意义下相同的值，输出即可。

模版题可以去luogu搜，我比较懒就不放传送门了。。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	ll fpow(ll a, ll b, ll mod) {
		ll res = 1;
		a %= mod;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	void Main() {
		ll a, p, b;
		auto BSGS = [&]()->ll{
			if (b % p == 1) return 0;
			ll m = sqrtl(p) + 1;
			unordered_map<ll, ll> mp;
			ll cur = b % p;
			for (ll i = 0; i < m; ++i) {
				mp[cur] = i;
				cur = cur * a % p;
			}
			ll am = fpow(a, m, p);
			cur = am;
			for (ll i = 1; i <= m; ++i) {
				if (mp.count(cur)) {
					ll ans = m * i - mp[cur];
					if (ans < p - 1) return ans;
				}
				cur = cur * am % p;
			}
			return -1;
		};
		while (cin >> a >> p >> b && (a || b || p)) {
			ll res = BSGS();
//			cout << a << ' ' << p << ' ' << b <<endl;
			if (res == -1) cout << "No Solution" << endl;
			else cout << res << endl;
		}
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

/*

901186563 448870829 79400778
0 0 0
*/

P2485 计算器

原题三合一，++经验。

但无解的情况要判清楚！

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	ll fpow(ll a, ll b, ll mod) {
		ll res = 1;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	ll BSGS(ll a, ll b, ll mod) {
		if (b % mod == 0 && a % mod == 0) return 1;
		if (a % mod == 0 && b % mod != 0) return -1;
		if (b % mod == 1) return 0;
		ll m = sqrtl(mod) + 1;
		unordered_map<ll, ll> mp;
		ll cur = b % mod;
		for (ll i = 0; i < m; ++i) {
			mp[cur] = i;
			cur = cur * a % mod;
		}
		ll am = fpow(a, m, mod);
		cur = am;
		for (ll i = 1; i <= m; ++i) {
			if (mp.count(cur)) {
				ll ans = i * m - mp[cur];
				if (ans < mod - 1) return ans;
			}
			cur = cur * am % mod;
		}
		return -1;
	}
	void Main(int id) {
		ll a, b, p;
		cin >> a >> b >> p;
		if (id == 1) {
			cout << fpow(a, b, p) << endl;
		} else if (id == 2) {
			if (a % p == 0){
				if (b % p == 0) cout<<0<<endl;
				else cout << "Orz, I cannot find x!" << endl;
			} 
			else cout << b * fpow(a, p - 2, p) % p << endl;
		} else {
			ll ans = BSGS(a, b, p);
			if (ans == -1) cout << "Orz, I cannot find x!" << endl;
			else cout << ans << endl;
		}
	}
}
int main() {
	CZW::init();
	int Test = 1, id;
	cin >> Test >> id;
	while (Test--)
		CZW::Main(id);
	return 0;
}

EXBSGS

比其原来就是不保证 $(a,p)=1$ 。

我们令 $g=(a,p)$ ，如果 $b$ $mod$ $g$ $\not=0$ 则无解，否则我们可以拆成：

$\frac{a}{g} \times a^{x-1} \equiv \frac{b}{g}$ $(mod$ $\frac{q}{g})$

重复上面过程，知道无解或者 $(a,p)=1$ ，显然操作次数在 $\log p$ 范围。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	constexpr ll inf = -1e18;
	ll fpow(ll a, ll b, ll mod) {
		ll res = 1;
		a %= mod;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	ll exgcd(ll a, ll mod, ll &x, ll &y) {
		if (!mod) {
			x = 1, y = 0;
			return a;
		}
		ll g = exgcd(mod, a % mod, y, x);
		y -= a / mod * x;
		return g;
	}
	ll BSGS(ll a, ll p, ll b) {
		ll m = sqrtl(p) +1;
		unordered_map<ll, ll> mp;
		ll cur = b;
		for (ll i = 0; i < m; ++i) {
			mp[cur] = i;
			cur = cur * a % p;
		}
		ll am = fpow(a, m, p);
		cur = am;
		for (ll i = 1; i <= m; ++i) {
			if (mp.count(cur)) {
				ll ans = m * i - mp[cur];
				if (ans < p - 1) return ans;
			}
			cur = cur * am % p;
		}
		return inf;
	}
	ll EXBSGS(ll a, ll p, ll b) {
		if (b % p == 1 % p) return 0;
		if (a % p == 0 && b % p == 0) return 1;
		ll x, y;
		ll g = exgcd(a, p, x, y);
		if (g > 1) {
			if (b % g) return inf;
			exgcd(a / g, p / g, x, y);
			ll inv = (x % (p / g) + (p / g)) % (p / g);
			return EXBSGS(a, p / g, b / g * inv % (p / g)) + 1;
		} else {
			return BSGS(a, p, b);
		}
	}
	void Main() {
		ll a, p, b;
		while (cin >> a >> p >> b && (a || p || b)) {
			a = (a % p + p) % p;
			b = (b % p + p) % p;
			ll res = EXBSGS(a, p, b);
			if (res < 0) cout << "No Solution" << endl;
			else cout << res << endl;
		}
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

无论是BSGS还是EXBSGS，我认为判无解，0和1最要注意（也有可能是我太弱了吧，在这上面挂了挺多发的）。

P3306

神秘推柿子题，由题意得：

$x_i=a_{i-1} \times x_1 + b \times \sum_{i=0}^{i-2}a^i (mod$ $p)$

最后自己手推一下就可以得到：

$a^{i-1} \equiv (t + b \times (a-1)^{-1}) \times(b \times (a-1)^{-1}+x_1)^{-1} (mod$ $p)$

因为 $p$ 为质数，一道BSGS的模板题。

但是，5min推柿子，花了60min调特判条件，绷不住了。。。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	ll fpow(ll a, ll b, ll mod) {
		ll res = 1;
		a %= mod;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	void Main() {
		ll p, a, b, x1, t;
		cin >> p >> a >> b >> x1 >> t;
		if (x1 == t) {
			cout << 1 << endl;
			return ;
		}
		if (a == 0) {
			if (b % p == t % p) cout << 2 << endl;
			else cout << -1 << endl;
			return ;
		}
		if (a == 1) {
			if (!b) cout << -1 << endl;
			else {
				ll ans = fpow(b, p - 2, p) * ((t - x1) % p + p) % p;
				cout << ans + 1 << endl;
			}
			return ;
		}
		auto BSGS = [&]()-> ll{
			if (b % p == 1 % p) return 0;
			if (a % p == 0 && b % p == 0) return 1;
			if (a % p == 0 && b % p != 0) return -1;
			ll m = sqrtl(p) + 1;
			unordered_map<ll, ll> mp;
			ll cur = b;
			for (ll i = 0; i < m; ++i) {
				mp[cur] = i;
				cur = cur * a % p;
			}
			ll am = fpow(a, m, p);
			cur = am;
			for (ll i = 1; i <= m; ++i) {
				if (mp.count(cur)) {
					ll ans = i * m - mp[cur];
					if (ans < p - 1) return ans;
				}
				cur = cur * am % p;
			}
			return -1;
		};
		ll val = b * fpow(a - 1, p - 2, p) % p;
		b = (val + t) % p * fpow(val + x1, p - 2, p) % p;
//		cout << a << ' ' << b << endl;
		ll ans = BSGS();
		cout << (ans == -1 ? ans : ans + 1) << endl;
	}
}
int main() {
	CZW::init();
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

/*
1
5 4 3 1 2
*/

整除分块

一个神秘 $\sqrt{N}$ 级别技巧。

考虑一个基础问题： $\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$

打表发现取值为分为 $\sqrt{n}$ 块，令 $l$ 为左端点，则 $r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ 。

为什么 $r$ 去这个数？我的理解是，当前我们处理的区间值为 $\lfloor \frac{n}{i} \rfloor$ ，而这个值在 $n$ 值域范围内最多有 $\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$ 这么多数。

再考虑，如果变成： $\sum_{i=1}^{n} i \times \lfloor \frac{n}{i} \rfloor$ ，怎么办？

显然，在一个区间内， $\lfloor \frac{n}{i} \rfloor$ 是不变的，变得是 $i$ ，用等差数列求和，或者前缀和都行。

P2261

根据余数性质 $n$ $mod$ $i=n -i \times \lfloor \frac{n}{i} \rfloor$ ，提出常量，就是一个上面板子题目

#include<bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	using lb = long double;
	void Main() {
		ll n, k; cin >> n >> k;
		ll ans = k * n, res = 0;
		ll l = 1, r = 0;
		while (l <= n) {
			if (k / l) r = min(k / (k / l), n);
			else r = n;
			res += (l + r) * (r - l + 1) / 2 * (k / l);
			l = r + 1;
		}
		cout << ans - res;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test = 1;
//	cin >> Test;
	while (Test--) CZW::Main();
	return 0;
}

P2260

比较爽的推柿子！

我们令 $n\le m$ ，

根据容斥原理和取模性质，得到：
$\sum_{i=1}^{n} \sum_{j=1}^{m} {(n-i\times \lfloor \frac{n}{i} \rfloor)\times (m-j\times \lfloor \frac{m}{j} \rfloor)}-\sum_{i=1}^{n}{(n-i\times \lfloor \frac{n}{i} \rfloor)\times (m-i\times \lfloor \frac{m}{i} \rfloor)}$

再推：

$(\sum_{i=1}^{n} {n-i\times \lfloor \frac{n}{i} \rfloor}) \times (\sum_{j=1}^{m}{m-j\times \lfloor \frac{m}{j} \rfloor})-n^2m+\sum_{i=1}^{n}n\times i \times \lfloor \frac{m}{i} \rfloor+\sum_{i=1}^{n}m \times i \times \lfloor \frac{n}{i} \rfloor-\sum_{i=1}^{n} {i^2 \times \lfloor \frac{n}{i} \rfloor\times \lfloor \frac{m}{i} \rfloor}$

这里我们发现遇到了二维分块，相当于有两行多段区间相交起来，我们处理时只用对分别的区间右端点取一个min即可。

注： $\sum_{i=1}^{n} {i ^ 2}=\frac{1}{6}\times n \times (n+1) \times (2\times n + 1)$

所以我们就这样做完了：

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	constexpr ll mod = 19940417, inv2 = 9970209, inv6 = 3323403;
//	ll exgcd(ll a, ll mod, ll &x, ll &y) {
//		if (!mod) {
//			x = 1, y = 0;
//			return a;
//		}
//		ll g = exgcd(mod, a % mod, y, x);
//		y -= a / mod * x;
//		return g;
//	}
	void Main() {
//		ll x, y;
//		exgcd(6, mod, x, y);
//		cout << (x % mod + mod) % mod<<endl;
//		return ;
		ll n, m;
		cin >> n >> m;
		ll k = min(n, m);
		ll ans1 = n * n % mod, ans2 = m * m % mod, ans3 = n * m % mod * k % mod;
		ans3 = (-ans3 % mod + mod) % mod;
		auto sum = [&] (ll len) ->ll {
			len %= mod;
			return len * (len + 1) % mod * (2 * len % mod + 1) % mod * inv6 % mod;
		};
		ll l = 1, r = 0;
		while (l <= n) {
			r = n / (n / l);
			ans1 = (ans1 - (l + r) % mod * (r - l + 1) % mod * inv2 % mod * (n / l) % mod + mod) % mod;
			l = r + 1;
		}
		l = 1;
		while (l <= m) {
			r = m / (m / l);
			ans2 = (ans2 - (l + r) % mod * (r - l + 1) % mod * inv2 % mod * (m / l) % mod + mod) % mod;
			l = r + 1;
		}
		l = 1;
		while (l <= k) {
			r = min (n / (n / l), m / (m / l));
			ll a = (l + r) % mod * (r - l + 1) % mod * inv2 % mod * (m / l) % mod;
			ll b = (l + r) % mod * (r - l + 1) % mod * inv2 % mod * (n / l) % mod;
			ll c = ((sum(r) - sum(l - 1)) % mod + mod) % mod * (n / l) % mod * (m / l) % mod;
			ans3 = (ans3 + ((a * n % mod + b * m % mod) % mod - c + mod) % mod) % mod;
			l = r + 1;
		}
		cout << (ans1 * ans2 % mod + ans3) % mod;
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

P6583

非常神秘的整除分块！

首先有一个结论，就是若一个分数（最简形式）分母只含质因数 $2$ 或 $5$ 时才是有限小数。

那就考虑化简分数，令 $d=\gcd(x,y)$ 且 $d\not|2$ 且 $d\not|5$ ，所以我们转化为 $\frac{a\times d}{b\times d}$ 。

考虑一个函数 $f(n)$ 表示 $[1,n]$ 有多少个数是形如 $2^a\times 5^b$ 。

如何推？

先考虑 $2^a\times 5^b\le n$ ，

所以 $5^b\le \frac{n}{2^a}$ ，

所以 $y\in [0,\log_5{\frac{n}{2^a}}]$ 。

枚举 $x$ 使得 $2^a\le n$ ，即可 $O(\log n)$ 求出这个东西，那这个东西有啥用呢？

朴素的看，我们可以枚举 $d$ ， $a$ 的取值范围为 $[1,\lfloor \frac{n}{d} \rfloor]$ ， $b$ 为其基础上只包含 $2$ ， $5$ 质因数。

所以对于一个 $d$ ，如果有 $cnt_b$ 个 $b$ 满足条件，则贡献为 $cnt_b \times \lfloor \frac{n}{d} \rfloor$ 。

所以 $Ans=\sum_{d=1}^{n} {[d\not| 2] [d\not |5]f(\lfloor \frac{n}{d} \rfloor) \times \lfloor \frac{n}{d} \rfloor}$ 。

注意到这么一坨东西也可以整除分块，按照 $\lfloor \frac{n}{d} \rfloor$ 值分块即可。

考虑到前面两个限制，我们考虑一个容斥，在区间 $[1,x]$ 内，满足 $d\not| 2$ 且 $d\not |5$ 的数有 $(x-\lfloor \frac{x}{2} \rfloor - \lfloor \frac{n}{5}\rfloor +\lfloor \frac{n}{10} \rfloor)$ 个。

这样就做完了。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	void Main() {
		ll n; cin>>n;
		auto get=[&](ll x) ->ll{
			ll res = 0;
			for (ll i = 0; (1ll << i) <= x; ++i){
				res += (ll)(log(x >> i) / log(5)) + 1;
			}
			return res;
		};
		auto sum=[&](ll x)->ll{
			return x - x / 2 - x / 5 + x / 10;
		};
		ll l = 1, r = 0;
		ll ans = 0;
		while(l <= n){
			r = n / (n / l);
			ans += (n / l) * (sum(r) - sum(l - 1)) * get(n / l);
			l = r + 1;
		}
		cout << ans;
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

原根

神秘知识点，定义可以去oi-wiki上了解，我感觉我没咋看懂，丢一个求原根的步骤吧

判定 $n$ 是否有原根：
根据数学定理，只有 $n = 2, 4, p^k, 2p^k$ （其中 $p$ 是奇素数， $k \ge 1$ ）这四种情况有原根。
求 $\varphi(n)$ 的质因数：
如果 $g$ 是 $n$ 的原根，则对于 $\varphi(n)$ 的任意质因数 $q$ ，都有 $g^{\frac{\varphi(n)}{q}} \not\equiv 1 \pmod n$ 。
求最小原根 $g_0$ ：
从 1 开始枚举 $g$ ，利用上面的性质判定，找到第一个满足条件的 $g$ 。最小原根通常很小（ $O(n^{1/4})$ 级别），所以枚举很快。
求出所有原根：
如果 $g_0$ 是一个原根，那么所有的原根集合为 $\{g_0^k \pmod n \mid \gcd(k, \varphi(n)) = 1, 1 \le k \le \varphi(n) \}$ 。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr int N = 1e6 + 5;
	ll primes[N], phi[N];
	int cnt;
	bool is[N];
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
		for (int i = 2; i < N; ++i) {
			if (!is[i]) primes[++cnt] = i, phi[i] = i - 1;
			for (int j = 1; i * primes[j] < N && j <= cnt; ++j) {
				is[i * primes[j]] = true;
				if (i % primes[j] == 0) {
					phi[i * primes[j]] = phi[i] * primes[j];
					break;
				}
				phi[i * primes[j]] = (primes[j] - 1) * phi[i];
			}
		}
	}
	ll fpow(ll a, ll b, ll mod) {
		ll res = 1;
		a %= mod;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	bool chk(ll n) {
		if (n == 2 || n == 4 ) return true;
		if (n % 2 == 0) n /= 2;
		if (n % 2 == 0) return false;
		for (int i = 1; i <= cnt && primes[i] * primes[i] <= n; ++i) {
			if (n % primes[i] == 0) {
				while (n % primes[i] == 0) n /= primes[i];
				return n == 1;
			}
		}
		return n > 1;
	}
	vec<ll> get(ll m) {
		vec<ll> f;
		for (int i = 1; i <= cnt && primes[i] * primes[i] <= m; ++i) {
			if (m % primes[i] == 0) {
				f.pb(primes[i]);
				while (m % primes[i] == 0) m /= primes[i];
			}
		}
		if (m > 1) f.pb(m);
		return f;
	}
	void Main() {
		ll n, d;
		cin >> n >> d;
		if (!chk(n)) {
			cout << 0 << endl << endl;
			return ;
		}
		ll m = phi[n];
		vec<ll> f = get(m);
		ll g0 = 1;
		for (ll g = 1; ; ++g) {
			if (__gcd(g, n) != 1) continue;
			bool ok = true;
			for (ll F : f) {
				if (fpow(g, m / F, n) == 1) {
					ok = false;
					break;
				}
			}
			if (ok) {
				g0 = g;
				break;
			}
		}
		vec<ll> ans;
		ll cur = 1;
		for (ll i = 1; i <= m; ++i) {
			cur = cur * g0 % n;
			if (__gcd(i, m) == 1) ans.pb(cur);
		}
		sort(ans.begin(), ans.end());
		cout << ans.size() << endl;
		for (size_t i = d - 1; i < ans.size(); i += d) cout << ans[i] << " ";
		cout << endl;
	}
}
int main() {
	CZW::init();
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

持续更新中（~~字符串有点不想更了咋办~~）......

有帮助，赞一个

去预览

0/2000

全部评论 4

prediction
您怎么这么强！

1周前来自浙江
1
🥥
您怎么这么强！

1周前来自上海
1
- Asdfre
  回复
  🥥
  /kel
  
  1周前来自广东
  0
Asdfre
@cjdst

1周前来自广东
1
- cjdst
  回复
  Asdfre
  ？？？？？
  
  1周前来自浙江
  0
- cjdst
  回复
  Asdfre
  求提单
  
  1周前来自浙江
  0
- Asdfre
  回复
  cjdst
  lyy拉的题单，私信丢你
  
  1周前来自广东
  0
Asdfre
dddddd

1周前来自广东
1