Текущ брой на Списание ИнфоМан
 


Есенен турнир 2004, Задача B1. ДЕЛИМОСТ

Уловието на задачата може да прочетете тук.

Решение

Разделяме числото P на прости множители. То се представя по един единствен начин като произведение на прости числа (т.нар. канонично представяне):

P = p1a1 . p2a2. p3a3 ... pkak

Освен това от дефиницията за факториел имаме:

N! = 1.2.3...N

  От условието знаем, че

  N! = PM .Z1, където Z1 е цяло число, т.е.

N! = (p1a1.M).(p2a2.M).(p3a3.M)...(pkak.M).Z1

 

Търсим максималното M, за което това равенство е изпълнено. N!, от своя страна, също може да бъде разложено канонично:

N! =(p1b1.p2b2.p3b3...pkbk.Z2

Тогава очевидно от горните две равенства и понеже M е максимално:

b1≥a1.M

b2≥a2.M

bn≥an.M

което е еквивалентно на

M≤b1/a1

M≤b2/a2

M≤bn/an

Откъдето следва, че M е минималното измежду числата bi/ai, където bi и ai са степените на числото pi съответно в N! и P. За да решим задачата трябва ефективно да можем да намерим, за някое просто число pi колко пъти се среща в P и колко пъти в N!. Първото е тривиално – делим P на pi докато P се дели целочислено на pi. По- трудната задача е да намерим числото bi. Лесно се доказва, че броят на числата по-малки или равни на N, които се делят на дадено число p са точно [N/p] ([x] – най-голямото цяло число, ненадвишаващо x). Да си поставим за задача да намерим колко са числатаT[k] от 1 до N включително, които се делят на pk но не се делят на pk+1, т.е. числа от вида q = pk.r, където rне се дели на p. Тъй като N! е произведение точно на числата от 1 до N включително, то очевидно

bi = Т[1].1 + T[2].2 + ... + T[s].s

където s е най- високата степен на срещане на p в N. Числата T[s] намираме лесно – T[s] = [N/ps].  Числото [N/ps-1] е точно броят на числата до N, които се делят на ps-1, но измежду тях има и числа, които се делят на ps. Тогава

T[s-1] = [N/ps-1] – T[s] = [N/ps-1] – [N/ps]

С аналогични разсъждения получаваме:

T[s-2] = [N/ps-2] – T[s-1] – T[s-2] = [N/ps-2] – ([N/ps-1] – [N/ps]) –  [N/ps]) = [N/ps-2] – [N/ps-1] 

T[s-3] = [N/ps-3] – T[s-1] – T[s-2] – T[s-3] = [N/ps-3] – [N/ps-2]

...

T[1] = [N/p] – [N/p2]

Така намерената формула се пресмята лесно и ефективно и по този начин се намира числото bi. Скоростта на това решение се определя от начина на разлагане на едно число на прости множители. За посочените ограничения е напълно достатъчно да се генерира масив с простите числа от 2 до  и след това да проверим на кои от тези прости числа се дели P. За всяко просто числоpi, на което P се дели намираме ai и bi и делим P на най-високата степен на pi, на която се дели целочислено. Избираме минимума от всички (bi/ai) и това е стойността на M. 

Забележка:Ако в крайна сметка след като обходим всички прости числа до , P е различно от 1, то очевидно P е просто число по-голямо от . Тогава е достатъчно да намерим колко пъти P ще се среща в N! и това е търсеният отговор.

Примерна реализация:

#include <stdio.h>

#define MAX 500000
#define MAXP 256

int primes;
int pr[MAXP];

int prime ( int n ) {
int i;
	for (i = 0;pr[i]*pr[i]<=n && i<primes;i++)
		if (n%pr[i]==0)
			return 0;
	return 1;
}

void gen_primes() {
int i;
	pr[0] = 2;
	primes = 1;
	for (i = 3;i*i<=MAX;i++)
		if (prime(i))
			pr[primes++] = i;
}

int get_occurrences(int what,int N) {
long long t = what;
int count = 1;
int sum = 0;
	while (N>=t) {
		sum+=(N/t-N/((long long)t*what))*count;
		t*=what;
		count++;
	}
	return sum;
}

int main () {
int min = 2000000000;
int N,P,i,power,oc;
	scanf("%d%d",&N,&P);
	gen_primes();
	for (i=0;i<primes && P!=1;i++)
		if (P%pr[i]==0) {
			power = 0;
			while (P%pr[i]==0) {
				P/=pr[i];
				power++;
			}
			oc = get_occurrences(pr[i],N);
			if (oc/power<min) {
				min = oc/power;
			}
		}
	if (P>1) { // ako P e prosto chislo,
	// po- goliamo ot koren ot 500000
		min = get_occurrences(P,N);
	}
	printf("%d\n",min);
	return 0;
}	

Автор: Слави Маринов


обратно към брой 27