12216- How Many bases?
Time limit: 3.000 seconds
A classical problem of number theory is “Find the number of trailing zeroes in NM, in base B”. This problem is quite conventional and easy. But a number can have same number of trailing zeroes in more than one base. For example, if decimal number 24 is written in 3, 4, 6, 8, 12 and 24 based number system, it will look like 80, 60, 40, 30, 20 and 10 respectively. So in all number systems it has only one trailing zero. Given a number NM, your job is to find out the number of integer bases in which it has exactly T trailing zeroes.
Input
The input file contains at most 10000 line of input. Each line contains three integers N (1 ≤ N ≤ 108), M (0< M≤ 107) and T (0< T ≤ 104). The meaning of N, M and T is given in the problem statement. Input is terminated by a line containing three zeroes, which obviously should not be processed for calculation.
Output
For each line of input produce one line of output. This line contains the serial of output followed by an integer NB, which is modulo 100000007 value of number of bases in which NM has exactly T trailing zeroes.
Sample InputOutput for Sample Input
24 11
100 200 10
23 18 2
000
Case 1: 6
Case 2: 312
Case 3: 3
题意: 输入n,m,k , 要你将n的m次方用某种进制表示后，其尾部正好有k
个0.求这样的进制的个数。
思路: 假设n的m次方用p进制表示后，其尾部正好有k个0. 其实就相当于
n^m % p^k = 0 && n^m % p^(k+1) != 0.
ans1 表示n的m次方用某种进制表示后，其尾部至少有k个0的进制的个数。
ans2 表示n的m次方用某种进制表示后，其尾部至少有k+1个0的进制的个数。
若fa 是n的一个质因子,有 tp *（fa^num）= n ; n^m中fa的个数为cnt=num*m个。
fa^cnt =fa ^ ( cnt/ k ) ^ k . 即 ans1=ans1*(cnt / k+1);
fa^cnt =fa ^ ( cnt/ (k+1) ) ^ (k+1) . 即 ans2=ans2*(cnt / (k+1)+1);
最终答案ans = ans1 – ans2 ;
#include <iostream>#include <cstdio>#define ll long longusing namespace std;const int mod = 100000007;ll ans1,ans2;int n,m,k,cnt;int main(){while(scanf("%d %d %d",&n,&m,&k)!=EOF){if(n==0 && m==0 && k==0) break;ans1=ans2=1;for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0){n/=i;cnt++;}cnt*=m;ans1=ans1*(cnt/k+1)%mod;ans2=ans2*(cnt/(k+1)+1)%mod;}}if(n!=1){ans1=ans1*(m/k+1)%mod;ans2=ans2*(m/(k+1)+1)%mod;}printf("Case %d: %lld\n",++cnt,(ans1-ans2+mod)%mod);}return 0;}
，偶尔会想，如果人生真如一场电子游戏，
