2228. Цвет

Бусинки n цветов соединены между собой в циклическое ожерелье из n бусинок (n ≤ 10⁹). Вам следует подсчитать количество различных ожерелий, которое можно получить. В ожерелье не обязательно использовать все n цветов. Повторениями, полученными в результате вращения ожерелья вокруг центра, следует пренебречь.

Вывести ответ по модулю p.

Вход. Первая строка содержит количество тестов x (x ≤ 3500). Каждая из следующих x строк содержит два числа n и p (1 ≤ n ≤ 10⁹, 1 ≤ p ≤ 30000).

Выход. Для каждого теста вывести ответ в отдельной строке.

Пример входа	Пример выхода
5 1 30000 2 30000 3 30000 4 30000 5 30000	1 3 11 70 629

РЕШЕНИЕ

теорема Пойа

Анализ алгоритма

При подсчете ожерелий следует пренебречь его вращениями, но не отображениями относительно осей симметрии. Бусинки можно красить k = n цветами. Количество различных ожерелий равно (учитывая что n = k)

=

В случае вычисления ответа по формуле

=

получим Time Limit.

Пример

Пусть количество бусинок равно n = 4, количество цветов равно k = 4. Тогда количество ожерелий равно

= = = = 70

Реализация алгоритма

Функция euler(n) вычисляет функцию Эйлера φ(n).

int euler(int n)

{

int i, result = n;

for(i = 2; i * i <= n; i++)

if (n % i == 0)

{

result -= result / i;

while (n % i == 0) n /= i;

}

if (n > 1) result -= result / n;

return result;

}

Вычисление степени числа по модулю: xⁿ mod p.

int power(int x, int n)

{

int res = 1;

x = x % p;

while(n)

{

if (n & 1) res = (res * x) % p;

x = (x * x) % p;

n >>= 1;

}

return res;

}

Основная часть программы. Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&p);

k = n; res = 0;

Перебираем делители i числа n от 1 до . Если i – делитель n, то n / i также будет делителем n.

for(i = 1; i * i < n; i++)

if (n % i == 0)

{

res = (res + euler(i) % p * power(k,n/i-1)) % p;

res = (res + euler(n/i) % p * power(k,i-1)) % p;

}

Отдельно обработаем случай, если n является полным квадратом.

if (i * i == n)

res = (res + euler(i) * power(k,i-1)) % p;

Выводим ответ res.

printf("%d\n",res);

}