SP1030题解

MsgNotFound · 2024-01-08 19:12:05 · 题解

一道很简单的找规律、模拟题。

思路分析

上来看 k\le2\times10^{12}，直接蒙圈，然后尝试着暴力找规律。

暴力代码如下：

#include<iostream>
using namespace std;
int main(){
    for(long long i=1;i<=100005;i++){
        if(i*i*i%1000==888)cout<<i<<' ';
    }
    return 0;
}

由于输出太长了，所以节选一部分，足以证明规律：

看到这里，你是不是发现一些规律了？拿计算器算算，发现每个数字之间相差都是 250！找出规律后，根据样例可以知道，第一个数字是 192，随后就可以写出代码了：

#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;
    long long k;// 数据量大，所以开long long 
    while(t--){
        cin>>k; 
        cout<<192+(k-1)*250;// 规律 
    }
    return 0; 
}

证明

声明：证明的思路来源于@laboba大佬。

在这之前，我们对 1000 进行一个分解质因数，可得 1000=2^3\times5^3。

首先，我们设需要求的数为 x，因此 x^3 的末三位数字为 888。我们在设一个大整数 A，这样可以求出 n^3=A\times1000+888。根据样例，第一个符合的数字是 192，我们就可以设 192^3=B\times1000+888，因为两个式子都有同样的项，所以可以用第一个式子减去第二个式子，就会得出以下结果：

n^3-192^3=(A-B)\times1000

根据立方差公式，a^3-b^3=(a-b)\times(a^2+a\times b+b^2)，又可以得出：

n^3-192^3=(n-192)\times(n^2+n\times192+192^2)=(A-B)\times1000

随后，我们开始枚举 n 除以 1 到 5 的余数。

n\equiv0(\bmod\ 5), (n^2+n\times192+192^2)\equiv4(\bmod\ 5)

n\equiv1(\bmod\ 5), (n^2+n\times192+192^2)\equiv2(\bmod\ 5)

n\equiv2(\bmod\ 5), (n^2+n\times192+192^2)\equiv1(\bmod\ 5)

n\equiv3(\bmod\ 5), (n^2+n\times192+192^2)\equiv4(\bmod\ 5)

n\equiv4(\bmod\ 5), (n^2+n\times192+192^2)\equiv3(\bmod\ 5)

枚举完成后，我们会惊奇的发现，无论 n 除以 5 余数是几， (n^2+n\times192+192^2) 除以 5 都不余 0。不过想要满足条件，(n^2+n\times192+192^2) 的值必须是 1000 的倍数，而 5^3 是 125 ，也是 1000 的倍数，所以想要满足条件，n^-192^3 必须被 125 整除，也就是 \lfloor n^3-192^3 \div 125 \rfloor =0。

继续：假设 n 为奇数，则 n^3-192^3 的值为奇数， (n^2+n\times192+192^2) 的值也是奇数，与题目要求不符，所以说，n 必须是偶数，这样，最终的结果才能被 1000 整除。所以说，