主要思路和推导
这道题还是比较有意思的(啊呀看了好久的题解才会写,真菜),主要就是把\(d\)转换成了:
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下:每一次约数被枚举出来的时候,只有互质的情况下才会被计数,避免了重复计数。 Continue reading →
这道题还是比较有意思的(啊呀看了好久的题解才会写,真菜),主要就是把\(d\)转换成了:
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下:每一次约数被枚举出来的时候,只有互质的情况下才会被计数,避免了重复计数。 Continue reading →
哇这道题还是很神仙的。
首先,有递推式:
\[ f_i = \left(\prod_{j = 1}^{k} f_{i – j}^{b_j}\right) \bmod p \]
题目会给出一个\(f_n=m\),且这个数列前面的项都是\(1\),可看作次数为\(0\)的常数项。我们会发现,对于\(f_j,j>k\),都可以写成\(f_k^{C}\),其中\(C\)是一个多项式。这个多项式可以通过线性递推得到:
\[ C_i = (\sum_{j = 1}^{k} b_jC_{i-j}) \mod (p-1) \]
看到数据范围,考虑用矩阵乘法在\(O(n^3 \log n)\)的时间内得到\(C_n\)。所以现在我们有:
\[ f_k^{C_k} \equiv m \;(mod \; p) \]
我们现在已知\(k,m,p,C_n\),我们现在要求\(f_k\)。考虑使用原根来搞。众所周知,998244353 的原根是 3。原根的幂可以填充整个模\(p\)剩余系,所以可以考虑把这个式子写成:
\[ (3^t)^{C_k} \equiv 3^s \;(mod \; p), \text{其中设}m = 3^s, f_k = 3^t \]
我们把离散对数搞下来,变成:
\[ t*C_k \equiv s \; (mod \; p-1) \]
这个用 BSGS 搞下就可以得出结果\(s\)。然后用 exgcd 算出同余方程的解(顺便判别有无解)。算出\(t\)之后快速幂一下输出。
// CF1106F.cpp #include <bits/stdc++.h> #define ll long long using namespace std; // TODO: Make it fit to the matrix power; const int MAX_MAT = 150, mod = 998244353; int n, m, k, ki[MAX_MAT]; struct matrix { ll mat[MAX_MAT][MAX_MAT]; void basify() { for (int i = 1; i <= k; i++) mat[i][i] = 1; } ll *operator[](const int &id) { return mat[id]; } matrix operator*(const matrix &mt) const { matrix ans; memset(ans.mat, 0, sizeof(ans.mat)); for (int i = 1; i <= k; i++) for (int j = 1; j <= k; j++) for (int mid = 1; mid <= k; mid++) ans.mat[i][j] = (ans.mat[i][j] + mat[i][mid] * mt.mat[mid][j] % (mod - 1)) % (mod - 1); return ans; } matrix operator^(const int &tim) const { matrix ans, bas = *this; ans.basify(); int ti = tim; while (ti) { if (ti & 1) ans = ans * bas; bas = bas * bas; ti >>= 1; } return ans; } }; ll quick_pow(ll bas, ll tim) { ll ans = 1; while (tim) { if (tim & 1) ans = ans * bas % mod; bas = bas * bas % mod; tim >>= 1; } return ans; } ll bsgs(ll a, ll y) { if (a == 0 && y == 0) return 1; if (a == 0 && y != 0) return -1; map<ll, ll> hsh; ll u = ceil(sqrt(mod)); for (int i = 0, x = 1; i <= u; i++, x = x * a % mod) hsh[y * x % mod] = i; ll unit = quick_pow(a, u); for (int i = 1, x = unit; i <= u; i++, x = x * unit % mod) if (hsh.count(x)) return i * u - hsh[x]; return -1; } ll exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } ll d = exgcd(b, a % b, x, y), z = x; x = y, y = z - (a / b) * y; return d; } ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); } ll solve(ll a, ll b, ll c) { if (b == 0) return 0; ll d = gcd(a, b); a /= d, b /= d; if (gcd(a, c) != 1) return -1; ll res, tmp; exgcd(a, c, res, tmp); res = res * b % c; res = (res + c) % c; return res; } int main() { scanf("%d", &k); for (int i = 1; i <= k; i++) scanf("%d", &ki[i]); scanf("%d%d", &n, &m); matrix B; for (int i = 1; i <= k; i++) B[1][i] = ki[i]; for (int i = 2; i <= k; i++) B[i][i - 1] = 1; B = B ^ (n - k); ll res = B[1][1], s = bsgs(3, m), ans = solve(res, s, mod - 1); if (ans == -1) puts("-1"); else printf("%lld", quick_pow(3, ans)); return 0; }
乍一看其实可以跟欧拉函数扯上关系。我们要求的是\(gcd(x,y) \in Prime, x, y \leq N\)的有序对个数。我们设那个质数为\(s\),则可以化为:
\[ x = sa, y = sb \\ gcd(a, b) = 1 \]
嗯,看到欧拉函数的影子了。对于每一个质数\(s\),它对答案的贡献是:
\[ 2 * \sum_{ 1 \leq i \leq \lfloor \frac{n}{s} \rfloor } \phi(i) – 1 \]
我来解释一下:因为\(x,y \leq n\),所以\(sa \leq n\),\(sb \leq n\),得:
\[ a,b \leq \frac{n}{s} \]
所以会有这么多对,考虑这个是有序对,所以乘上二,再删除掉\((i,i)\)这样的有序对重复即可得到答案。注意,可以用前缀和欧拉函数值来进行优化。
// BZ2818.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 10000005; ll n, phi[MAX_N]; bool isPrime[MAX_N]; int main() { //memset(isPrime, true, sizeof(isPrime)); scanf("%lld", &n); for (int i = 2; i <= n; i++) phi[i] = i; for (int i = 2; i <= n; i++) if (!isPrime[i]) for (int j = i; j <= n; j += i) { if (j != i) isPrime[j] = true; phi[j] = phi[j] / i * (i - 1); } phi[1] = 1; for (int i = 2; i <= n; i++) phi[i] += phi[i - 1]; long long ans = 0; for (int i = 2; i <= n; i++) if (!isPrime[i]) ans += 2 * phi[n / i] - 1; printf("%lld", ans); return 0; }
嗯,我这种数学菜鸡来写数学题的确很难过。
首先分析题意,明显的就是提供一些线性同余方程,然后求解。但是,与中国剩余定理不同的是,这道题不保证模数互质。
\[ x \equiv a_1 (mod\ m_1) \\ x \equiv a_2 (mod\ m_2) \\ x \equiv a_3 (mod\ m_3) \\ \dots \\ x \equiv a_i (mod\ m_i) \]
但是我们仍然可以用古老的扩展欧几里得算法来解这个问题,合并方程即可。
假设我们正在解第\(k\)个方程,设\(m=\prod_{i=1}^{k-1}\),\(x\)为满足\(1\)~\(k-1\)个方程的解。我们知道,\(tm+x\)为前\(k-1\)个方程的通解,那么我们只需要在这一轮求出\(k\)并更新答案即可,也就是解:
\[ tm_{k-1} + x_{k-1} \equiv a_k(mod\ m_k) \\ tm_{k-1} + m_k y \equiv a_k – x_{k-1}(mod\ m_k) \]
放进 \(exgcd\) 里面解下即可。
// POJ2891.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 1e6 + 200; ll exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } ll d = exgcd(b, a % b, x, y), z = x; x = y, y = z - (a / b) * y; return d; } int main() { ll n; while (~scanf("%lld", &n)) { ll x, y, a, b, k; scanf("%lld%lld", &a, &b); ll lcm = a, ans = b; bool flag = true; n--; while (n--) { scanf("%lld%lld", &a, &b); b = (b - ans % a + a) % a; ll d = exgcd(lcm, a, x, y); if (b % d) flag = false; else k = x * (b / d); ans += k * lcm; lcm = lcm / d * a; ans = (ans % lcm + lcm) % lcm; } if (flag) printf("%lld\n", ans); else puts("-1"); } return 0; }
这道题可以将式子化简为:
\[ nk-\sum_{i=1}^{n} \lfloor \frac{k}{i} \rfloor * i \]
第一部分乘积即可,第二部分直觉告诉我们\(\lfloor \frac{k}{i} \rfloor\)在一段连续的\(i\)上会相等,也就是说,是分段的。每一段的和可以直接用等差数列来求就行。我们来探究一下段区间的左右端点。我们假设目标区间是\([i,?]\),那么这一段区间的值肯定就是\(\lfloor \frac{k}{i} \rfloor\),反求一下那么右端点就是\( \lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor \)。可以证明右端点大于等于左端点。等差数列求和即可。
// BZ1257.cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll n, k; int main() { scanf("%lld%lld", &n, &k); ll ans = n * k, gx; for (int x = 1; x <= n; x = gx + 1) { gx = (k / x) ? min(k / (k / x), n) : n; // x ~ gx same; ans -= (k / x) * (gx - x + 1) * (gx + x) / 2; } printf("%lld", ans); return 0; }