校测 2024 0930 数学

0-30-0,数学还只打了暴力，菜就多练

Problem 1. facsum

省流: \(f(n) =(\sum\limits_{d\mid n}\varphi(d))^m(\sum\limits_{d\mid n}\sigma_0(d)\mu(\frac{n}{d})\frac{n}{d})\)
求 \(\sum\limits_{i = 1}^nf(i)\bmod 1e9+7\)
大概是把
前面的区域以后再来探索吧

Problem 2. group

Mr.Hu 最近在研究等比数列，即形如：
\(a^1, a^2,...,a^n,...\)
现在，Mr.Hu 想知道，对于给定的非负整数 \(a\)，上面这个无穷数列在摸 \(mod\) 意义下有多少项是本质不同
的。(保证 \(gcd(a, mod) = 1\))。

Input

第 1 行一个整数：\(T\) ，表示数据组数。接下来 \(T\) 行，每行两个整数：\(a, mod\)。

Output

对于每组数据，输出一行，包含一个整数，表示模意义下本质不同的数有多少个。

Note

• 对于 30% 的数据，\(0 ≤ a ≤ 103，1 ≤ mod ≤ 103\) ；
• 对于 100% 的数据，\(0 ≤ a ≤ 2 × 109，1 ≤ mod ≤ 2 × 109，且保证 gcd(a, mod) = 1，1 ≤ T ≤ 100。\)

分析

对于模意义下的等比数列最小循环节长度，考虑循环节到最后一项必定为 \(1\) , 想到欧拉定理 \(a^{\varphi(n)}\equiv 1 \pmod p\)，直接暴力求 \(\varphi(n)\) ,枚举其因子 \(x\) 是否满足 \(a^x\equiv 1 \pmod p\),快速幂优化一下，时间复杂度 \(O(T\sqrt n\log(m))\)

AC代码：

#include<bits/stdc++.h>
using namespace std;inline int read() {int f = 1, otto = 0;char a = getchar();while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}while(isdigit(a)) {otto = (otto << 1) + (otto << 3) + (a ^ 48);a = getchar();}return f * otto;
} int a, mod;
int ans = 0;int getphi(int x) {int as = x;for(int i = 2; i * i<= x; i++) {if(x % i == 0) {while(x % i == 0) x /= i;as = as / i * (i - 1) ;	//公式 }}if(x > 1) as = as / x * (x - 1);return as;
}int qpow(long long x, int y) {long long as = 1;while(y) {if(y & 1) (as *= x) %= mod, y--;(x *= x) %= mod, y >>= 1;}return as;
}void solve() {if(a == 0) return printf("0\n"), void(0);int phi = getphi(mod); ans = phi;for(int i = 1; i * i <= phi; i++) {if(phi % i == 0){if(qpow(a, i) == 1) ans = min(ans, i);else if(qpow(a, phi / i) == 1) ans = min(ans, phi / i);}}return printf("%lld\n", ans), void(0);
}int main() {freopen("group.in", "r", stdin);freopen("group.out", "w", stdout);int T = read();while(T--) {a = read(), mod = read();solve();}return 0;
}

Problem 3. ccount

未完待续，敬请期待