Description
定义 (f(x)) 表示 (x) 的各个数位之和。现在要求 (sum_{i=l}^rf(i)mod a)。
显然 ans=solve(l,r)%a; if(ans<=0) ans+=a;
会在 (sum_{i=l}^rf(i)equiv 0pmod a) 时输出错误。给定 (a),请你构造一个 Hack 数据。
(1leq aleq 10^{18}),构造出的 (l,r) 需满足 (1leq lleq rleq 10^{200}),同时 (sum_{i=l}^rf(i)mod a=0)。
Solution
定义 (g(x)=sum_{i=1}^xf(i)),则 (sum_{i=l}^rf(i)=g(r)-g(l-1))。
首先可以发现,对于 (1leq x<10^{18}),有:
(displaystyle f(x+10^{18})-f(x)=1)
也就是说,当 ([l,r]) 从 ([x+1,x+10^{18}]) 变成 ([x+2,x+10^{18}+1]) 时(整体增大 (1)),由于 (f(x+10^{18}+1)-f(x+1)=1),因此结果会增加 (1)。
那么,当 ([l,r]) 从 ([1,10^{18}]) 变成 ([x+1,x+10^{18}]) 时(整体增大 (x)),结果会增加 (x)。即:
(displaystyle sum_{i=k+1}^{k+10^{18}}equiv g(10^{18})+kpmod a)
若 (g(10^{18})equiv xpmod a),取 (k=a-x),那么:
(displaystyle sum_{i=a-x+1}^{a-x+10^{18}}equiv 0pmod a)
则可取 ([l,r]) 为 ([a-x+1,a-x+10^{18}])。考虑如何求出 (x)。
不难发现,(g(10^x)=45 imes x imes 10^{x-1}+1)。所以 (g(10^{18})=45 imes 18 imes 10^{17}+1)。
#include<bits/stdc++.h> #define int long long using namespace std; int a,x; signed main(){ scanf("%lld",&a),x=1ull*((int)1e17%a*45%a*18%a+1)%a; printf("%lld %lld ",a-x+1,a-x+(int)1e18); return 0; }