【神秘题整数溢出】牛客小白月赛71 C-猫猫与数列

Myth丶恋晨 2024-03-22 09:03 69阅读 0赞

**被教育了**

**学到了一些只有我不知道的常识**

[C-猫猫与数列\_牛客小白月赛71(重现赛) (nowcoder.com)][C-_71_ _nowcoder.com]

题意：

![70ba299ea4e64439b6dfd2ed99037057.png][]

思路：

直接模拟即可

值得注意的是，他在算数列的过程中可能会爆long long，因此在算的时候注意开\_\_int128，这样就算爆long long也能和1e18比较

![c01625124f4046338307b5593e4dd18c.png][]

\_\_int128可以四则运算，但是不能输入输出，因此要专门写一个函数实现输入输出

Code：

#include <bits/stdc++.h>
    using namespace std;
    inline __int128 read(){
        __int128 x = 0, f = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9'){
            if(ch == '-')
                f = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9'){
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * f;
    }
    inline void print(__int128 x){
        if(x < 0){
            putchar('-');
            x = -x;
        }
        if(x > 9)
            print(x / 10);
        putchar(x % 10 + '0');
    }
    int main(void){
        __int128 a = read();
        __int128 b = read();
        print(a + b);
        cout << endl;
        return 0;
    }

关于这道题：

#include<bits/stdc++.h>
    using namespace std;
    const long long M=1e18;
    long long A[10005];
    __int128 calc(__int128 a,long long b){
    	__int128 res=1;
    	while(b>0){
    		if(b&1)res=res*a;
    		if(res>M||a>M)return M+10;
    		a=a*a;
    		b>>=1;
    	}
    	return res;
    }
    int main(){
        
        
    	scanf("%lld %lld",&A[1],&A[2]);
    	int n=2;
    	for(int i=3;i;i++){
    		A[i]=calc(A[i-2],A[i-1]);
    		if(A[i]>M){
    			n=i-1;
    			break;
    		}
    	}
    	printf("%d\n",n);
    	return 0;
    }

[C-_71_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/56661/C
[70ba299ea4e64439b6dfd2ed99037057.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/029ee91e2d26438f9806075c5235e582.png
[c01625124f4046338307b5593e4dd18c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c88b275b693b488fac1619658c672646.png