Euleonora Pt. 2
Лятна Информатическа Школа, 2009
Time Limit: 0.5s, Memory Limit: 64MiB
Сблъсквали ли сте се някога с продавачка в магазин, която не може да сметне колко ресто трябва да ви върне, когато й давате 42 лева при сметка 37? Ако не сте, то Елеонора със сигурност е – най-вече поради честите си посещения в моловете (където продавачките мислят, че "логаритъм" е вид крем за лице, а Форд-Белман и Форд-Фулкерсон могат да се намерят в салоните на Мото-Пфое).

От друга страна Ели е значително по-интелигентна. Докато продавачката се справя със "сложните" сметки, тя е измислила начин да запълва времето си. За всяко положително цяло число N тя смята колко на брой по-малки или равни на него положителни цели числа има, които са взаимно-прости с N - тоест за колко различни AiN е изпълнено GCD(Ai, N) = 1. Например, за числото 9 нейната функция би върнала 6, тъй като 1, 2, 4, 5, 7 и 8 са взаимно-прости с 9. Тя е нарекла функцията, която връща този брой, "функция на Ойлеонора" и я бележи като phi(N).

Да смята тези числа на ум за нея не е проблем, но понякога сметките на продавачката се бавят твърде много (я си представете, че има и стотинки!), за това тя изчислява цели интервали от числа наведнъж, сумирайки намерените стойности. Например за интервала [5, 12] имаме phi(5) = 4, phi(6) = 2, phi(7) = 6, phi(8) = 4, phi(9) = 6, phi(10) = 4, phi(11) = 10, phi(12) = 4. Съответно, търсената сума е 4 + 2 + 6 + 4 + 6 + 4 + 10 + 4 = 40.

Вие решавате да впечатлите Ели, като напишете програма, която да може да се конкурира с нейните способности!
Вход
На единствения ред на стандартния вход ще бъдат дадени двете цели числа A и B, задаващи интервала, от който се интересува Ели.
Изход
На стандартния изход изведете сумата на phi(i) в интервала [A, B].
Ограничения
  • 1 ≤ AB ≤ 1,000,000
Примерен Вход Примерен Изход
5 12 40
123456 987654 291871808870
Мрън!