校测 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

未完待续，敬请期待