背单词——冰雹猜想

发布时间:2024年01月22日

小明正在为四级做准备,他计划至少背 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;
}

文章来源:https://blog.csdn.net/m0_74403543/article/details/135739820
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。