在文化課晚自習想出來的奇怪玩意兒。

Description

令 \((1+\sqrt{2})^n=e(n)+\sqrt{2}f(n)\)，其中 \(e(n),f(n)\) 都是整數，顯然有 \((1-\sqrt{2})^n=e(n)-\sqrt{2}f(n)\)。令 \(g(n)=\operatorname{lcm}(f(1),f(2),\dots,f(n))\)。

給定兩個正整數 \(n,p\)，其中 \(p\) 是質數，并且保證 \(f(1),f(2),\dots,f(n)\) 在模 \(p\) 意義下均不為 \(0\)，請計算 \(\sum \limits_{i=1}^n i\times g(i)\) 模 \(p\) 的值。

Analysis

先定義一些簡化運算的符號：\(f(T)=\{f(x) | x \in T\}\)，\(\gcd(T)\) 表示 \(T\) 中所有元素的最大公因數，\(\dfrac{T}w0obha2h00=\left\{\left.\dfrac{x}w0obha2h00\right|x \in T\right\}\)，\(d|T\) 表示是否所有 \(T\) 中元素均為 \(d\) 的倍數。

先從題目直接給出的條件入手可以得到 \(f(n)\) 的通項公式：\(2\sqrt2f(n)=(1+\sqrt2)^n-(1-\sqrt2)^n\)。

然后發現一個常見的數列性質：\(x|y \Rightarrow f(x)|f(y)\)。證明可以使用因式定理。

令 \(kx=y\)，則只需說明 \((1+\sqrt2)^x-(1-\sqrt2)^x|(1+\sqrt2)^{kx}-(1-\sqrt2)^{kx}\)。

令 \(a=(1+\sqrt2)^x,b=(1-\sqrt2)^x\)，即證 \(a-b|a^k-b^k\)，顯然成立。

結果發現必要性著證不了，這雖然也不知道他是不是充要條件，也不用管了。

假如這是充要條件，那么就一定有 \(\gcd(f(T))=f(\gcd(T))\)。

令 \(S=[1,n]\cap \Z\)，則

于是完全可以把 \(T\) 的枚舉移到指數上去。

現 f(d) 已經簡單到到極致了，只考慮指數優化，發現特別可以莫比烏斯反演。

后面這一坨仔細想想，\([dk|T]\) 實際上限制了 \(T\) 的元素取值范圍必須為 \(dk\) 的倍數，在 \(dk\) 確定后 \(T\) 的元素種數也就確定了，這就特別爽。易知后面這一大坨相當于 \([dk\leq n]\)，值顯然為 \(1\)。

所以最后的式子是 \(\displaystyle \prod_{d=1}^nf(d)^{\sum _{k=1}^{n/d} \mu(k)}\)。

直接預處理 \(\mu(k)\) 前綴和 \(\mu'(k)\) 就……可以了嗎？

他不是只求一個 \(g(n)\)，而是要求 \(n\) 個 \(g(i)\)。但這樣做單次復雜度是 \(\mathcal O(n)\) 的。

固定 \(d\)，\(\lfloor\dfrac{i}w0obha2h00\rfloor\) 隨著 \(i\) 的增大變化次數總共只有 \(\dfrac{n}w0obha2h00\) 次，枚舉 \(d\) 再枚舉這幾次變化，就是調和級數復雜度 \(\mathcal O(n\log n)\)。

Solution

具體就實現一個差分，這里修改了過后會影響后面的 \(g(i)\)，最后前綴積一下就行了。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define eb emplace_back
#define MOD(x) ((x) >= mod ? (x)-mod : (x))
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6+5;
int n, mod, p[N], m;
inline LL qpow(LL a, int b, LL res = 1) {
	for (; b; b >>= 1, a=a*a%mod) if (b&1) res = res*a%mod;
	return res;
}
bool v[N];
LL mu[N];
inline void prework(int n) {
	mu[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!v[i]) p[++m] = i, mu[i] = -1;
		for (int j = 1; j <= m && p[j]*i <= n; ++j) {
			v[i*p[j]] = 1, mu[i*p[j]] = -mu[i];
			if (i % p[j] == 0) {
				mu[i*p[j]] = 0;
				break;
			}
		}
	}
}
LL f[N], c[N], inv[N];
inline LL calc(int x, int op) {
	if (op==0) return 1;
	if (op < 0) return inv[x];
	return f[x];
}
inline void solve() {
	cin >> n >> mod; f[1] = c[1] = 1;
	for (int i = 2; i <= n; ++i) f[i] = ((f[i-1]<<1)+f[i-2])%mod, c[i] = 1, inv[i] = qpow(f[i], mod-2);
	for (int d = 2; d <= n; ++d)
		for (int i = 1; i*d <= n; ++i)
			(c[i*d] *= calc(d, mu[i])) %= mod;
	LL ans = 1;
	for (int i = 2; i <= n; ++i) c[i] = c[i-1]*c[i]%mod, ans = (ans+c[i]*i)%mod;
	cout << ans << '\n';
}
signed main() {
	FASTIO;
	int _;
	cin >> _;
	prework(1e6);
	while (_--) solve();
	return 0;
}

補充

前邊假設了一個結論 \(x \mid y \Leftrightarrow f(x)\mid f(y)\)。現在來證明。

充分性已經證過了。

必要性考慮證明 \(x \nmid y \Rightarrow f(x) \nmid f(y)\)。

假設 \(y=kx+r(k\in \N,0<r<x)\)。

即證 \((1+\sqrt 2)^x-(1-\sqrt 2)^x \nmid (1+\sqrt 2)^{kx+r}-(1-\sqrt 2)^{kx+r}\)。

令 \(a=(1+\sqrt 2)^x,b=(1-\sqrt 2)^x\)。

要證 \(a-b \nmid a^k(1+\sqrt 2)^r-{b^k}(1-\sqrt 2)^r\)，只需證明 \(a-b\) 不是右式的因式即可。

反證法，假設 \(a-b\) 是右式的因式，則根據因式定理，\(a=b\) 時，右式為 \(0\)，即 \(a^k(1+\sqrt 2)^r-b^k(1-\sqrt 2)^r=0\)，進一步地，\((1+\sqrt 2)^r-(1-\sqrt 2)^r=0\)，顯然在 \(r\in(0,x)\) 時不可能成立，所以矛盾了！。

對于廣義斐波那契數列 \(f_{n+1}=af_n+bf_{n-1}\) 上面那個結論其實是一個普遍性質。

通過這個結論可以導出：\((f_a,f_b)=f_{(a,b)}\) 和 \([f_a,f_b]=f_{[a,b]}\)（不常用）。