D. Тоонууд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Үнэхээр энгийн нэг өдөр Валера сургуульдаа явжээ (ажлын өдрүүдэд түүнд үүнээс өөр явах ёстой газар байхгүй). Математикийн хичээл дээр түүний дуртай багш хатагтай Эванс хуваагчдын талаар сурагчдаа хэлжээ. Валера математикт дуртайгаа үл хамааран, уг сэдвийг сонирхолтой гэж үзсэнгүй. Түүнчлэн, түүнийг хичээлийн дундуур унтахаар үнэхээр уйтгартай байв. Зөвхөн сургуулийн хонхны чанга жингэнэх чимээ түүний сайхан зүүдийг тасалдуулжээ.

Мэдээж хэрэг, үнэ цэнэтэй материал болон багшийн тайлбарууд мартагдав. Тэгсэн хэдий ч, Валера ямар нэг замаар эсвэл өөрөөр гэрийн даалгавраа хийх ёстой. Тэрээр мэдээж хэрэг шинэ материалыг мэдэхгүй учраас, тэрээр уг даалгаврыг өөрөө хийж чадахгүй. Тиймээс таны тусламжийг хүсжээ. Та бол энэ бүхний дараа ч түүний сайн найз ба иймд та туслахаас татгалзаж чадахгүй юм.

Валера-ын гэрийн даалгавар нь зөвхөн нэг бодлоготой ба гэсэн хэдий ч энэ нь маш энгийнээр боловсруулагдсан бөгөөд энгийн бодолттой биш юм. Үүний өгөгдөл нь дараах байдлаар харагдана: Хэрэв бид $[a;b]$ завсар дахь бүх эерэг бүхэл тоонуудыг авч үзвэл уг бодлого нь тэдгээрийн хамгийн бага хуваагч нь тодорхой бүхэл тоо $k$ (та хуваагчийг 1-тэй тэнцүү гэж бодох хэрэггүй) байх уг завсарт орших тоонуудын тоог тоолох юм. Өөрөөр хэлбэл, та $[a;b]$ завсар дахь $2$-оос $k - 1$-ын хооронд байх ямар ч тоонд хуваагдахгүй гэхдээ $k$-д хуваагдах тоонуудын тоог тоолох юм.

Оролт

Ганц мөрөнд 3-н эерэг бүхэл тоо $a$, $b$, $k$ ($1 ≤ a ≤ b ≤ 2*10^{9}, 2 ≤ k ≤ 2*10^{9}$) өгөгдөнө.

Гаралт

Өгөгдсөн бодлогын хариултыг ганц мөрөнд хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
1 10 2
Гаралт
5
Оролт
12 23 3
Гаралт
2
Оролт
6 19 5
Гаралт
0

Тэмдэглэл

Бодлогын жишээнүүдийн тайлбар:

Эхний жишээний хариулт нь $2, 4, 6, 8, 10$ тоонууд байна.

2-дахь жишээний хариулт нь -- $15, 21$

3-дахь жишээнд тийм тоонууд байхгүй байна.

Сэтгэгдлүүдийг ачааллаж байна...