Muallif: __thecrash__
A. Shokolad bo'lagi
Vaqt limiti: 1000 ms Xotira limiti: 128 mb
Laylo tug'ilgan kuniga katta shokolad plitkasi sovg'a oldi. Plitka \(n\) qator va \(m\) ustundan iborat bo'lib, har bir katakchasi \(1 \times 1\) o'lchamli kichik kvadrat.
Laylo shokoladni darhol yeb qo'ymoqchi emas. U plitkadan faqat bitta kvadrat shaklidagi bo'lak kesib olmoqchi. Kesish faqat katakchalar orasidagi chiziqlar bo'ylab bajariladi. Bo'lak \(1 \times 1\), \(2 \times 2\), \(3 \times 3\) va hokazo o'lchamda bo'lishi mumkin, faqat plitkaga sig'sa bas.
Quyidagi rasmda \(2 \times 3\) o’lchamli plitkadan kvadrat bo’lak kesib olishning ba’zi usullari ko’rsatilgan:
Ikki usul har xil hisoblanadi, agar kesib olingan bo'laklar o'lchami yoki joylashuvi bilan farq qilsa.
Laylo kvadrat bo'lakni necha xil usulda kesib olishi mumkin?
Kiruvchi ma'lumotlar
Yagona qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n, m \le 10^6\)) — plitkaning qatorlari va ustunlari soni.
Chiquvchi ma'lumotlar
Bitta son — kvadrat bo'lakni kesib olish usullari soni.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
2 3 |
8 |
2 |
3 4 |
20 |
Izoh
Birinchi misolda plitka \(2 \times 3\):
- \(1 \times 1\) o'lchamli bo'lakni \(6\) xil joydan kesib olish mumkin;
- \(2 \times 2\) o'lchamli bo'lakni \(2\) xil joydan kesib olish mumkin (chapdan yoki o'ngdan);
- \(3 \times 3\) bo'lak plitkaga sig'maydi.
Jami \(6 + 2 = 8\) usul.
