Hack it!

Emin Ayar'a teşekkür ederiz.

Soru Metni

İkbal codeforceste sınav olurken şöyle bir soru karşısına çıktı.
f(x) x sayısının rakamları toplamını ifade etsin. ( örneğin , f(1234) = 1 + 2 + 3 + 4 )
Diğer bir deyişle :

ikbal problemi hemen çözdü ve hack aramaya başladı. önüne şöyle bir c++ kodu çıktı
 
ans = solve(l, r) % a;
if (ans <= 0)
    ans += a;
kod sadece l ile r arasının f değerleri toplamı a modunda 0 ise çalışmıyor.
Diğer bir deyişle:


GİRDİ
tek satırda bir integer a(1<=a<=10^18)
ÇIKTI
iki sayı l ve r (1 ≤ l ≤ r < 10^200) -- l ve r sayıları 0 ile başlayamaz ve her zaman bir çözümün var olduğu garanti edilmekte. birden fazla çözüm varsa herhangi birini yazabilirsiniz

Sample test(s)

input

46

output

1 10

input

126444381000032

output

2333333 2333333333333

Soru Linki: codeforces.com/contest/468/problem/C

Çözüm Metni:

1 ile (10^k)-1 arasındaki sayıların f değerleri toplamını bulması kolay.
şöyle ki k basamaktan birini k nın 1 lisi ile seçip ona 0..9 aralığındaki sayılardan birini koyarım. geriye kalan k-1 basamak 10^(k-1) farklı değer alır.
o halde 1....(10^k)-1 aralığındaki sayıların f değerleri toplamı 45*k*10^(k-1).

başlangıç olarak l yi 1 r yi ise 10^18 seçiyoruz.
şu anki toplamın moddaki değeri şuna eşittir;
ans=45*18*(10^17)+1 % a

eğer biz l ve r yi 1 er arttırırsak ans da bir artacaktır.

çünkü toplamdan eksilen sayı f(l) ve toplama eklenen sayı f(l+10^18) olur.
f(l+10^18)-f(l)=1 dir çünkü l+10^18 l nin soluna bir tane 1 konulmuş halidir.

eğer ans ı a ya ulaşıncaya kadar artırırsak mod a da sıfır olan bi aralık bulmuş oluruz.

Çözüm Kodu:

#include <bits/stdc++.h>
using namespace std;

typedef long long int Lint;
Lint a;

int main(){
    cin >> a;
    Lint l=1,r=1e18;
    Lint ans=(((9*(5*(9*(2*(Lint)1e17)%a)%a)%a)%a)+1)%a;
    cout << l+(a-ans) << ' ' << r+(a-ans) << endl;
    return 0;
}