HOJ--12500 Faculty Dividing Powers[수론]

Faculty Dividing Powers
Time Limit: 4000ms, Special Time Limit:10000ms, Memory Limit:65536KB
Total submit users: 40, Accepted users: 22
Problem 12500 : No special judgement
Problem description
Fred Faculty and Paul Power love big numbers. Day after day Fred chooses a random integer n and he computes n!. His friend Paul amuses himself by computing several powers of his randomly chosen integer k like k2, k3 and so on. On a hot summer day, Fred and Paul got really, really bored, so they decided to play a joke on their buddy Dave Divider. Fred chooses a random integer n while Paul chooses a random integer k. They want Dave to find the biggest integer i such that ki divides n! without a remainder, otherwise they will throw a cake in Dave's face. Because Dave does not like cakes in his face, he wants you to help him finding that integer i.
Input
The first line contains the number of test cases t (1 ≤ t ≤ 100). Each of the following t lines contains the two numbers n,k (2 ≤ n ≤ 1018, 2 ≤ k ≤ 1012) separated by one space.
Output
For each test case, print the maximum integer i on a separate line.
Sample Input

2

5 2

10 10

Sample Output

3

2

Judge Tips
Be careful with overflows in this problem (use 64 bit integers, avoid multiplications which will lead to overflow).
Problem Source
GCPC 2011
 
 
 
n을 주고 k가 가장 큰 i를 구하면 n!%k^i == 0 …
가장 간단한 상황을 가정하면...k는 질수...요구n!=1*2*3...*n...k의 배수에서 쉽게 볼 수 있다...K가 하나 있는데...K의 제곱에 K가 2개가 있는데...K의 세제곱에 K가 3개... 그럼 n!중k의 개수는 n/k+n/(k^2)+n/(n^3)이다.가장 큰 i...
한 걸음 넓혀서...만약 k가 비질수라면...그런데 질인자가 하나밖에 없어서...8, 9125 같은 거... n을 먼저 구할 수 있어요!그중에 몇 개의 질인자가 있는지, x로 설정하면... 그러면 몇 개의 k가 있는지...바로 i=x/p...p는 k가 기질인수의 몇 번을 가리키는지...
최종적으로 문제가 요구하는 임의의 수를 넓히는 경우..k=a1^k1 *a2^k2 *a3^k3...an^kn 그중 a1, a2...an은 질수...n을 계산할 수 있다!a1,a2,a3,an...이 몇 개 있고 k를 구성하려면 k1,a1이 필요해...k2개 a2...kn개 an...그럼 n(a1)/k1, n(a2)/k2...n(an)/kn...중에 제일 작은 게 답...
 
에서
 

 1 #include<iostream>

 2 #include<cmath>

 3 using namespace std;

 4 

 5 bool p[1000010];

 6 __int64 precord[1000010];

 7 __int64 pcnt=0;

 8 void init()

 9 {

10     memset(p,false,sizeof(p));

11     for(int i=2;i<=500004;i++)                      //   false

12         if(p[i]==false)

13             for(int j=i+i;j<=1000009;j+=i)

14                 p[j]=true;

15     for(int i=2;i<=1000008;i++)

16         if(p[i]==false)

17             precord[pcnt++]=i;

18 }

19 

20 __int64 min(__int64 a,__int64 b)

21 {

22     if(a>b)

23         return b;

24     return a;

25 }

26 

27 __int64 krecord[100000];

28 __int64 krecordcnt[100000];

29 

30 int main()

31 {

32     init();

33     int t;

34     __int64 n,k;

35     scanf("%d",&t);

36     while(t--)

37     {

38         memset(krecord,0,sizeof(krecord));

39         memset(krecordcnt,0,sizeof(krecordcnt));

40         scanf("%I64d%I64d",&n,&k);

41         

42         __int64 cnt=0;

43         __int64 temp=k;

44         for(int i=0;i<pcnt;i++)

45         {

46             if(precord[i]>temp)

47                 break;

48             if(temp%precord[i]==0)

49             {

50                 krecord[++cnt]=precord[i];

51                 while(temp%precord[i]==0)

52                 {

53                     krecordcnt[cnt]++;

54                     temp/=precord[i];

55                 }

56             }

57         }

58         if(temp!=1)

59         {

60             krecord[++cnt]=temp;

61             krecordcnt[cnt]=1;

62         }

63 

64         __int64 ans=-1;

65         __int64 pp;

66         __int64 count;

67         for(int i=1;i<=cnt;i++)

68         {

69             pp=krecord[i];

70             count=0;

71             while(1)

72             {

73                 count+=n/pp;

74                 if (n/krecord[i]>=pp)

75                     pp*=krecord[i];

76                 else

77                     break;

78             }

79             count/=krecordcnt[i];

80             if(ans==-1)

81                 ans=count;

82             else

83                 ans=min(ans,count);

84         }

85         printf("%I64d
",ans);

86     }

87     return 0;

88 }