Есенен турнир 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;
}
Автор: Слави Маринов
обратно към брой 26
|