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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #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) 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;}