小明正在为四级做准备,他计划至少背 n 个新单词。
为了完成这个目标,小明决定在每天结束前背一些新单词,具体来说:
第 1 天结束前,小明会背 m 个新单词;
第 i 天 (i≥2) 结束前,小明会根据第 i?1 天背的单词数计算第 i 天背多少个新单词。
假设小明在第 i?1 天背了 t 个新单词:
如果 t 是奇数,小明将会在第 i 天结束前背 3t+1 个新单词;
如果 t 是偶数,小明将会在第 i 天结束前背 2t 个新单词。
现在小明想知道按照这个方式背单词,最早在第几天结束时累计背了至少 n 个新单词。
输入
输入一行,包含两个整数 n,m (1 ≤ n ≤ 1e12,1 ≤ m ≤ 1000),分别代表小明计划背的新单词总数和小明第一天背的新单词数量。
输出
输出一行,包含一个整数 d ,代表小明在第 d 天结束时累计背了至少 ?n 个新单词。
Input
100 50
Output
3
解析:
冰雹猜想
一个正整数x,如果是奇数就乘以3再加1,如果是偶数就直接除以2,这样经过若干次数,这个数最终会回到1。
无论这个过程中的数值如何庞大,最终都会像瀑布一样迅速坠落。在经过若干次的变换之后也必然会到纯偶数:4-2-1的循环之中。据日本和美国的数学家攻关研究,在小于7e11的所有的正整数中,都符合这个规律。
虽然无法证明冰雹猜想是否完全正确,但是在 m 的数据范围下一定是正确的。
所以本题在枚举到 m 为1,2或4的时候,就可以三个为一组打包处理。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,m;
void solve()
{
cin>>n>>m;
int cnt=0;
while (n>0)
{
n -=m;
cnt++;
if (m&1) m=3*m+1;
else m /=2;
if (m==1||m==2||m==4)
{
cnt +=n/7*3;
n=n%7;
}
}
cout<<cnt;
}
signed main()
{
ios;
int T=1;
//cin>>T;
while (T--) solve();
return 0;
}