啥玩意,诈骗题还能这么诈骗。
\(f(X)\) 就是角谷猜想(冰雹猜想)所需的步数。根据角谷猜想,定义函数 \(g\):
\[g(X)= \begin{cases} \frac{X}{2},&2\mid X\\ 3X+1,&2\nmid X \end{cases} \]则显然有 \(f(g(X))=f(X)-1\)。样例二已经给出了 \(f(X)=1000\) 的解 \(X=1789997546303\),而 \(P\) 的范围是 \([0,1000]\),根据上面的结论递推即可求出 \(f(X)=P\) 的解。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 1e3+5;
ll n, ans[N];
int main() {
ans[1000] = 1789997546303LL;
per(i, 999, 0) {
if(ans[i+1] & 1) ans[i] = 3 * ans[i+1] + 1;
else ans[i] = ans[i+1] / 2;
}
scanf("%lld", &n);
printf("%lld\n", ans[n]);
return 0;
}
标签:std,問題,nikkei2019ex,题解,ll,ans,define,1000
From: https://www.cnblogs.com/ruierqwq/p/AT_nikkei2019ex_e.html