給出 2n 個數，求最大的 x 滿足 x!%M = 0 ，其中 M = a1^b1*a2^b2*a3^b3…*an^bn 。
Output
For each test case output the result x in one line.
Source
2010 Asia Regional Hangzhou Site Online Contest
#?include?<stdio.h>
#?include?<string.h>
#?include?<math.h>
#?define?N?101
typedef?long?long?int?LL;
int?n;
/*******************************************************/
int?p[50],?top?=?0;
int?isPrime(int?x)
{
????????????????int?i;
????????????????if?(x%2==0)?return?x==2;
????????????????if?(x%3==0)?return?x==3;
????????????????if?(x%5==0)?return?x==5;
????????????????for?(i?=?7;?i?<?x;?i?+=?5)
????????????????????????????????if?(x%i?==?0)?return?0;
????????????????return?1;
}
void?pre(void)
{
????????????????int?i;
????????????????for?(i?=?2;?i?<?N;?++i)
????????????????????????????????if?(isPrime(i))?p[top++]?=?i;
}
/*******************************************************/
LL?pn[50];
void?init(void)
{
????????????????int?i,?j,?x;
????????????????LL?cnt;
????????????????LL?num;
????????????????memset(pn,?0,?sizeof(pn));
????????????????scanf("%d",?&n);
????????????????for?(i?=?0;?i?<?n;?++i)
????????????????{
????????????????????????????????scanf("%d%I64d",?&x,?&num);
????????????????????????????????for?(j?=?0;?j?<?top;?++j)
????????????????????????????????{
????????????????????????????????????????????????if?(x%p[j]?==?0)
????????????????????????????????????????????????{
????????????????????????????????????????????????????????????????cnt?=?0;
????????????????????????????????????????????????????????????????while?(x%p[j]==0)?++cnt,?x/=p[j];
????????????????????????????????????????????????????????????????pn[j]?+=?cnt*num;
????????????????????????????????????????????????}
????????????????????????????????}
????????????????}
}
LL?Max(LL?x,?LL?y)
{
????????????????return?x>y???x:y;
}
LL?mypow(int?pr,?int?cnt)
{
????????????????LL?ret?=?1;
????????????????while?(cnt?>?0)?--cnt,?ret?*=?pr;
????????????????return?ret;
}
LL?cal(int?pr,?LL?tot)
{
????????????????int?tmp;
????????????????LL?ppow?=?0,?temp;
????????????????while?(tot?>?0)
????????????????{
????????????????????????????????tmp?=?(int)floor(log(tot*(pr-1)+1)/log(pr))+1;
????????????????????????????????while?((mypow(pr,?tmp)-1)/(pr-1)?>?tot)?--tmp;
????????????????????????????????temp?=?mypow(pr,?tmp);
????????????????????????????????ppow?+=?temp;
????????????????????????????????tot?-=?(temp-1)/(pr-1);
????????????????}
????????????????return?ppow;
}
void?solve(void)
{
????????????????int?i;
????????????????LL?ans?=?0;
????????????????for?(i?=?0;?i?<?top;?++i)?if?(pn[i]?!=?0)
????????????????????????????????????????????????ans?=?Max(ans,?cal(p[i],?pn[i]));
????????????????printf("%I64d\n",?ans);
}
int?main()
{
????????????????int?T;
????????????????pre();
????????????????scanf("%d",?&T);
????????????????while?(T--)?init(),?solve();
????????????????return?0;
}
posted on 2012-09-08 16:01
yajunw 閱讀(181)
評論(0) 編輯 收藏 引用