给出 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 阅读(162)
评论(0) 编辑 收藏 引用