【Codeforces】 CF468C Hack it!
题目链接
CF方向
Luogu方向
题目解法
令 ∑ i = 1 1 e 18 f ( i ) ≡ g ( g < a ) ( m o d a ) \sum_{i=1}^{1e18}f(i)\equiv g(g<a)(mod \;a) ∑i=11e18f(i)≡g(g<a)(moda)
那么 ∑ i = 2 1 e 18 + 1 f ( i ) ≡ g + 1 \sum_{i=2}^{1e18+1}f(i)\equiv g+1 ∑i=21e18+1f(i)≡g+1
同理 ∑ i = x 1 e 18 + x − 1 f ( i ) ≡ g + x − 1 \sum_{i=x}^{1e18+x-1}f(i)\equiv g+x-1 ∑i=x1e18+x−1f(i)≡g+x−1,其中 x < 1 e 18 x<1e18 x<1e18
考虑何时 g + x − 1 ≡ 0 g+x-1\equiv 0 g+x−1≡0
当 x x x 取 a − g + 1 a-g+1 a−g+1 时, ∑ i = a − g + 1 1 e 18 + a − g f ( i ) ≡ 0 ( m o d a ) \sum_{i=a-g+1}^{1e18+a-g}f(i)\equiv 0(mod\;a) ∑i=a−g+11e18+a−gf(i)≡0(moda)
所以 [ a − g + 1 , 1 e 18 + a − g ] [a-g+1,1e18+a-g] [a−g+1,1e18+a−g] 是一组合法的解
考虑求 g g g
每一位都可以从 0 0 0 取到 9 9 9,很好求, g = 18 ∗ 45 ∗ 1 0 17 + 1 = 81 ∗ 1 0 18 + 1 g=18*45*10^{17}+1=81*10^{18}+1 g=18∗45∗1017+1=81∗1018+1
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mul=1e18;
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
signed main(){int a=read();int g_1=mul%a*9%a*9%a;printf("%lld %lld",a-g_1,mul+a-g_1-1);return 0;
}