C. Hack it! time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Little X has met the following problem recently.
Let's define f(x) as the sum of digits in decimal representation of number x (for example, f(1234) = 1 + 2 + 3 + 4). You are to calculate
Of course Little X has solved this problem quickly, has locked it, and then has tried to hack others. He has seen the following C++ code:
ans = solve(l, r) % a;
if (ans <= 0)
ans += a;
This code will fail only on the test with
. You are given number a, help Little X to find a proper test for hack. Input
The first line contains a single integer a (1 ≤ a ≤ 1018).
Output
Print two integers: l, r (1 ≤ l ≤ r < 10200) — the required test data. Leading zeros aren't allowed. It's guaranteed that the solution exists.
Examples input
46
output
1 10
input
126444381000032
output
2333333 2333333333333 題意：
定義f(x)為x在十進制下的各位數字之和。
給定a，需要你給出一個l，r(1 <= l <= r <= 1e200)使得(f(l) + ... +f(r))能被a整除。
題目確定有解。
(1 <= a <= 1e18)
題解：
姿勢1：[一套尺取+二分連招]
令s(x) = f(1)+f(2)+…+f(x)。
我們隻需找到s(R)%a = s(L-1)%a就美滋滋了
我們使用二分查詢找到最小的且滿足g(R)>=a
的值R, 接下來令L=1,然後跑一個雙指針,調整
L,R的值即可。至于s(x)怎麼求，我們把每一個
數位對答案的貢獻加起來即可。
姿勢2：[構造]
注意到f(x+1e18)=f(x)+1。
故s(x+1e18)=s(1e18)+s(x)+x。
即s(x+1e18)-s(x) = s(1e18)+x
讓 s(1e18)+x%a==0,x= a-s(1e18)%a
L = a-s(1e18)%a+1，R = L + 1e18- 1
于是一組合法解就神不知鬼不知覺地構造出來了
代碼請有興趣的讀者自行完成~
方法1:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
ll get(ll x)
{
ll ans=0;
for(ll i=1;i<=x;i*=1ll*10)
{
int d=(x/i)%10;
ll q=x/(1ll*10*i);
ans+=i*q*45;
rep(j,1,d) ans+=j*i;
ll t=x-(x/i)*i;
ans+=(t+1)*d;
}
return ans;
}
ll get1(ll x)
{
ll ans=0;
while(x)
{
ans+=x%10;
x/=10;
}
return ans;
}
int main()
{
ll a;
scanf("%lld",&a);
ll l=0,r=1e17,ans=-1;
while(l<=r)
{
ll m=(l+r)/2;
if(get(m)>=a)
ans=m,r=m-1;
else l=m+1;
}
l=1,r=ans;
ll now=get(ans);
while(now!=a)
{
if(now>a) now-=get1(l++);
else if(now<a) now+=get1(++r);
}
printf("%lld %lld\n",l,r);
return 0;
}
方法2:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
ll get(ll x)
{
ll ans=0;
for(ll i=1;i<=x;i*=1ll*10)
{
int d=(x/i)%10;
ll q=x/(1ll*10*i);
ans+=i*q*45;
rep(j,1,d) ans+=j*i;
ll t=x-(x/i)*i;
ans+=(t+1)*d;
}
return ans;
}
int main()
{
ll a;
scanf("%lld",&a);
ll t=get(1e17)%a;
ll l=a-t+1,r=l+1e17-1;
printf("%lld %lld\n",l,r);
return 0;
}