題意：
? ? ? 輸入兩個整數(shù)n,m（1<m<5000,0<n<10000）求最小的k使得m^k是n!的因子。


思路：
? ? ?比較容易想，一開始手殘wa了好幾次，我們直接求出m和n!的素數(shù)因子和個數(shù)就行了，假如s1[a]表示的是n!的素數(shù)因子a的個數(shù)，s2是m的，則Ans=min(Ans ,s1[a]/s2[a]);這個應該不用解釋，很好理解吧！




#include<stdio.h>
#include<string.h>


int Pri[11000] ,pt;
int mark[11000];
int s1[11000] ,s2[11000];


void DBPri()
{
? ? memset(mark ,0 ,sizeof(mark));
? ? mark[1] = 1;
? ? pt = 0;
? ? for(int i = 2 ;i <= 10000 ;i ++)
? ? {
? ? ? ? if(!mark[i])
? ? ? ? {
? ? ? ? ? ? Pri[++pt] = i;
? ? ? ? ? ? for(int j = i + i ;j <= 10000 ;j += i)
? ? ? ? ? ? mark[j] = 1;
? ? ? ? }
? ? }
}


int main ()
{
? ? DBPri();
? ? int t ,cas = 1 ,i ,j ,n ,m;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d %d" ,&m ,&n);
? ? ? ? memset(s1 ,0 ,sizeof(s1));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? int now = i;
? ? ? ? ? ? for(j = 1 ;Pri[j] <= now && j <= pt ;j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? while(now % Pri[j] == 0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? now /= Pri[j];
? ? ? ? ? ? ? ? ? ? s1[Pri[j]] ++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }




? ? ? ? memset(s2 ,0 ,sizeof(s2));
? ? ? ? int mm = m;
? ? ? ? for(i = 1 ;Pri[i] <= mm && i <= pt ;i ++)
? ? ? ? if(mm % Pri[i] == 0)
? ? ? ? {
? ? ? ? ? ? while(mm % Pri[i] == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s2[Pri[i]] ++;
? ? ? ? ? ? ? ? mm /= Pri[i];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int Ans = 100000;
? ? ? ? for(i = 1 ;Pri[i] <= m && i <= pt ;i ++)
? ? ? ? if(m % Pri[i] == 0)
? ? ? ? {
? ? ? ? ? ? if(Ans > s1[Pri[i]] / s2[Pri[i]])
? ? ? ? ? ? Ans = s1[Pri[i]] / s2[Pri[i]];
? ? ? ? }


? ? ? ? printf("Case %d:\n" ,cas ++);
? ? ? ? if(Ans == 0) printf("Impossible to divide\n");
? ? ? ? else ?printf("%d\n" ,Ans);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的UVA10780幂和阶乘的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。