Masala #G8AL0DVWHL
f(x)*f(x)*x
\(x\) sonining chiroyliligi \(g(x)\) bilan belgilanadi. U quyidagicha hisoblanadi:
\[g(x) = f(x) * f(x) * x\]Bu yerda \(f(x)\) - \(x\)sonda ishlatilgan turli raqamlar soni. Masalan: \(f(1220) = 3\);\(f(93) = 2\); \(f(9876543210) = 10\). Sizga \(L, R\) hamda \(MOD\) beriladi. Sizning vazifangiz \([L, R]\) oralig'ida joylashgan barcha natural sonlarning chiroyliligini yig'indisini topish. Boshqa so'zlar bilan aytganda, quyidagini hisoblang:
\[\sum_{x=l}^{r} g(x)\]Natija juda ham katta bo'lishi mumkin. Shu sabab javobning \(MOD\) ga bo'lgandagi qoldig'ini chop eting.
Kirish faylida \(T (1 \le T \le 500)\) - testlar soni kiritiladi.
Keyingi \(T\) ta qatorning har birida 3 ta natural sonlar - \(L, R (1 \le L \le R \le 10^{200})\) va \(MOD(2 \leq MOD \leq 500)\)sonlari kiritiladi.
- Subtask #1: \(T \le 10\); \(L = 1\); \(R \le 10^6\) (8 ball)
- Subtask #2: \(T \le 1\); \(R-L \le 10^6\) (12 ball)
- Subtask #3: \(T \le 1\); \(R \le 10^{18}\) (20 ball)
- Subtask #4: \(T \le 2\); \(R \le 10^{50}; MOD \leq 200\) (30 ball)
- Subtask #5: Hamma testlar uchun \(MOD = const\), ya'ni \(MOD_i = MOD_j \ (1 \le i, j \le T)\) (30 ball)
Har bir test uchun alohida qatorda natijani chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 1 5 300 1 10 300 1 150 300 |
15 85 32 |
| 2 |
1 1234567790 1234567890 13 |
4 |
| 3 |
1 1234 123412341234 315 |
234 |
| 4 |
3 1 100 349 100 1000 349 1000 100000000000000000000 349 |
83 147 231 |
1-namunaviy test, 1-subtaskning 1-testiga to'g'ri keladi.
2-namunaviy test, 2-subtaskning 1-testiga to'g'ri keladi.
3-namunaviy test, 3-subtaskning 1-testiga to'g'ri keladi.
4-namunaviy test, 5-subtaskning 1-testiga to'g'ri keladi.
Telegram kanalimizga obuna bo'ling