[CoE R4 B/Stoi2041] 龙拳

· · 题解

题面

找规律

首先我们发现 g(2n)=n，此时有 f(2n)=2n+n=3n。

同样地，当 n 为奇数时，g(3n)=n，此时有 f(3n)=3n+n=4n。

这时候有趣的地方来了，4n 是一个偶数，因此 f^{(1)}(4n)=6n,f^{(2)}(4n)=9n。

也就是说，当 n 为奇数时，f^{(3)}(3n)=9n。

发现了什么？n 为奇数且为三的倍数时，重复三次此操作，就是将 n 乘以了 3，而乘以 3 以后 n 仍然满足“是奇数且是三的倍数”这个条件，那么又可以进行新一轮的循环。

按照这个规律推下去，你会发现当 n 满足上面所说的条件且时，f^{(i+3x)}(n)=3^xf^{(i)}(n)。

也就是 f^{(i)}(n)\mid f^{(i+3x)}(n)。

并且还会你发现 f^{(i)}(n)\mid f^{(i+k)}(n) 的充分必要条件就是 k=3x。

那输出 -1 的情况就是 k 不是 3 的倍数的情况了。

不过这里只是 n 为奇数且是三的倍数的情况，其它情况呢？

其它情况可以分为两类：

  1. 不妨设 $n=2^ab$ 时，那么此时一定有 $f^{a}(n)=3^ab$。 那就变成了之前的情况了。 当然也可能提前就能让 $n$ 满足进行循环的条件，比如 $n=2,6,12$ 的答案都是 $0$。 这个不是很难推，只要让 $n=4\cdot3^xy$ 或者 $n=2\cdot3^xy$ 或者 $n=3^xy(x>0)$，都能直接进入循环。 最后答案是 $\max(a-2,0)$。
  2. 显然 $g(n)$ 也是奇数，那么 $f(n)=n+g(n)$ 一定是偶数。 那就变成了第一种情况了。 即答案为 $\max(a-2,0)+1$。

那我们只需要对于每一个 n 求出 g(n) 就行了。

显然用欧拉素数筛可以提前预处理出来。

代码：

#include<bits/stdc++.h>
#define N 30000005 
using namespace std;
vector <int> prime;
bool vis[N];int g[N];
int T,n,k;
int main(){
    for(int i(2);i<N;++i){
        if(!vis[i]){prime.push_back(i);g[i]=1;}
        for(int j(0);j<prime.size()&&i*prime[j]<N;++j){
            vis[i*prime[j]]=1;g[i*prime[j]]=i;
            if(!(i%prime[j])) break;
        }
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        if(k%3) puts("-1");
        else{
            int cnt(0),flg(0);
            if(n%2&&n%3) n=n+g[n],flg=1;
            while(n&1^1) n>>=1,++cnt;
            printf("%d\n",max(cnt-2,0)+flg);
        }
    }
    return 0;
}