题目大意是给出一个K和L，求在[2, L)范围内有没有整数能整除K。
K很大，L<=10^6。
一开始我预处理了素数表，然后枚举[2, L)以内的素数，用大整数求余的方法判断是不是K的质因子，TLE。
将K改为万进制，溢出，WA。
改成千进制即可AC。
以下是我的代码：
/*
* Author: lee1r
* Created Time: 2011/8/25 10:29:17
* File Name: poj2635.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define Half(x) ((x)>>1)
#define Lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
bool scanf(int &num)
{
char in;
while((in=getchar())!=EOF && (in>'9' || in<'0'));
if(in==EOF) return false;
num=in-'0';
while(in=getchar(),in>='0' && in<='9') num*=10,num+=in-'0';
return true;
}
const int kMaxn(1100000);
int cnt,Prime[kMaxn+7];
bool isPrime[kMaxn+7];
void GetPrime()
{
cnt=0;
for(int i=1;i<=kMaxn;i++)
isPrime[i]=true;
for(int i=2;i<=kMaxn;i++)
{
if(isPrime[i])
Prime[++cnt]=i;
for(int j=1;j<=cnt && i*Prime[j]<=kMaxn;j++)
{
isPrime[i*Prime[j]]=false;
if(i%Prime[j]==0)
break;
}
}
}
int Mod(int *a,int n,const int L)
{
int re(0);
for(int i=1;i<=n;i++)
re=(re*1000+a[i]%L)%L;
return re;
}
int main()
{
GetPrime();
string S;
int a[100],n;
int L;
while(cin>>S>>L && (S!="0" || L))
{
n=0;
if(S.size()%3)
{
n++;
a[n]=0;
for(int i=0;i<S.size()%3;i++)
a[n]=a[n]*10+S[i]-'0';
}
for(int i=S.size()%3;i<S.size();i+=3)
{
n++;
a[n]=0;
for(int j=i;j<i+3;j++)
a[n]=a[n]*10+S[j]-'0';
}
int ans(-1);
for(int i=1;Prime[i]<L;i++)
if(Mod(a,n,Prime[i])==0)
{
ans=Prime[i];
break;
}
if(ans==-1)
printf("GOOD\n");
else
printf("BAD %d\n",ans);
}
return 0;
}
posted on 2011-08-25 11:12
lee1r 阅读(341)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论