Решение задачи " Покраска плиток" с Codeforces

С пояснением   Просмотров: 27


В последнее время Уджан стал весьма ленивым, но наконец-то решил привести свой двор в порядок. Сначала он решил покрасить тропинку от своего дома до ворот.

Тропинка состоит из n последовательных плиток, пронумерованных от 1 до n. Уджан покрасит каждую из плиток в некоторый цвет. Он считает, что тропинка эстетична, если каждые две различные плитки с номерами i и j такими, что |j−i| является делителем числа n строго большим 1, покрашены в одинаковые цвета. Формально, любые две плитки с номерами i и j должны быть покрашены в одинаковый цвет, если |i−j|>1 и nmod|i−j|=0 (где xmody — это остаток при делении x на y).

Уджан хочет украсить своё место. В какое наибольшее количество цветов Уджан может покрасить тропинку таким образом, чтобы она была эстетичной?

Код

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long g,a;cin>>a;
	g=a;
	for(long long i=2;i*i<=a;i++)
	{
		if(a%i==0)
		{
			g=__gcd(g,i);
			g=__gcd(g,a/i);
		}
	}
	cout<<g;
}

         

 Администратор Photo Автор: Администратор


Если n=pk для какого-то простого p, то тогда ответ равен p цветам. Тогда просто надо покрасить все плитки с номерами i(modp) в цвет i. Так как любой делитель d числа n больше 1 делится на p, то любые две плитки i и i+d будут покрашены в одинаковый цвет. К тому же, если первые p плиток покрашены в c разных цветов, то следующие p плиток будут покрашены в те же c цветов, поэтому ответ не может превосходить p.

Если же n=pq для p,q>1 таких, что gcd(p,q)=1, тогда ответ равен 1. Рассмотрим любые две разных позиции i,j. Докажем, что их цвет должен совпадать. По китайской теореме остатов, существует такой 1≤x≤n, что x≡i(modp) и x≡j(modq). Поэтому, обе плитки i и j должны быть покрашены в тот же цвет, что и плитка x. Значит, все плитки должны быть покрашены в один и тот же цвет.

Чтобы проверить, который случай из двух выполняется, используем слеlующий алгоритм:

Сначала проверяем, является ли n простым. Используем стандартный O(n−−√) алгоритм.
Иначе, если n=pk для k>1, тогда p должен быть по крайней мере n−−√≤106. Тогда мы можем найти наименьший делитель p числа n, больше 1, так как он не превышает 106. Тогда делим n на наибольшую степень p. Если n=pk, тогда n просто станет 1; иначе n останется больше 1, тогда он делится на какое-то другое простое, отличное от p.
Время работы: O(sqrt(n)).

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться