Description

给定一个数的标准分解\(N= \prod_{i=1}^n p_i^{q_i}\)

其中\(p_i \le 10^5, q_i \le 10^9\)

求最小的\(x\)使得\(\varphi^x(N) = 1\) 即求这个数进行多少次\(\varphi\)后得到1

Analysis

\(\varphi\)的性质还是经常与2有关的

比若说任意\(\varphi\)两次就一定会除掉一个因子2

所以\(\varphi\)的次数为\(O(\log)\)

此题就是利用类似这样的性质

\(\varphi\)的次数为只与过程中\(2\)的总数有关

(1) 如果存在\(2\), 每次只能恰好消掉一个

(2) 对于一个奇质数因子, \(\varphi\)以下会产生至少一个\(2\), 以及若干个新的奇质数

(3) 只要奇质数还存在, 该回合内就会产生至少一个2

(4) 消完\(2\)需要的次数\(=\)因此\(2\)产生的次数 \(\ge\) 进行的回合数

(5) 最后会剩下\(2^q\), 恰好\(q\)步消完

于是我们之用求出产生2的次数即可,设为 \(f(n)\)

\(f(2)=1\)

\(f(奇质数) = f(奇质数-1)\)

\(f(pq) = f(p) + f(q)\)

特别的当\(N\)不含2因子时, 需要一步来产生2, 然后2才开始不断的消, 所以答案+1

Code

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <cctype>

#include <cmath>

#define rep(i,a,b) for (int i = (a); i <= (b); ++i)

using namespace std;

const int M = 1e5 + 7;

typedef long long LL;

inline int ri(){

	int x = 0; bool f = 1; char c = getchar();

	for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;

	for (; isdigit(c); c = getchar()) x = x*10+c-48;

	return f ? x : -x;

}

int tcas, n;

int prime[M], cnt;

bool notprime[M];

int f[M];

void init(){

	notprime[1] = 1;

	for (int i=2; i<M; ++i){

		if (!notprime[i]) {

			prime[++cnt] = i;

			if (i == 2) f[i] = 1;

			else f[i] = f[i-1];

		}

		for (int j=1; j<=cnt; ++j){

			if (1LL * prime[j] * i >= M) break;

			int t = prime[j] * i;

			notprime[t] = 1;

			f[t] = f[i] + f[prime[j]];

			if (i % prime[j] == 0) break;

		}

	}

}

int main(){

	tcas = ri();

	init();

	while (tcas--){

		n = ri();

		LL ans = 0, havtwo = 0;

		rep (i, 1, n){

			int x = ri(), y = ri();

			ans += 1LL * f[x] * y;

			havtwo |= (x == 2);

		}

		if (!havtwo) ans++;

		printf("%lld\n", ans);

	}

	return 0;

}

巴特西

bzoj 2749 - 外星人

Description

Analysis

Code

最新文章

热门文章