ACM素因子钱多多TimeLimit:1000MSMemoryLimit:32768K\x05\x05\x05\x05\x05\x05\x05\x05\x05TotalSubmit:6(3users)\x05\x05\x05\x05\x05\x05\x05\x05\x05TotalAccepted:2(2users)\x05\x05\x05\x05\x05\x05\x05\x05\x05Rating:\x05\x05\x05\x05\x05\x

Question

ACM 素因子
钱多多
Time Limit:1000 MS Memory Limit:32768 K
\x05\x05\x05\x05\x05\x05\x05\x05\x05Total Submit:6(3 users) \x05\x05\x05\x05\x05\x05\x05\x05\x05Total Accepted:2(2 users) \x05\x05\x05\x05\x05\x05\x05\x05\x05Rating:\x05\x05\x05\x05\x05\x05\x05\x05\x05Special Judge:No
Description
Woods和他的GirlFriend（GF）去银行取钱,Woods拿出一沓银行卡问GF：“想取多少都行,说吧.”GF说：“你看着办吧,难道我喜欢什么样的数字你还不了解么?”
这下Woods可难办了.他当然知道不喜欢2,3,5,但是GF还有N个不喜欢的数字,所以Woods取出钱的数目M不能只和这N+3个数字有关（即素因子只包含这N+3个数字的数她都不喜欢）你能帮Woods判断一下他取出来的钱数M能否让GF满意吗?
Input
多组测试数据.第一行两个整数N,M,（1

Answer 1

实际上. 这题就是普通的素数分解. 先求出素数表, 然后根据这个表进行分解.
最后注意要使用unsigned int(int会溢出) 也就够了.
代码提交情况:
1502 Accepted 248K 0MS G++ 1.29K
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 70000, MAXM = 50;
char prime[MAXN]; // 存放素数表. 如prime[i] = 1, 则 i 是素数
unsigned int q[MAXM]; // 存放分解出来的因子.
int qn;
void Prime() // 筛法求素数表
{
int i, j;
for (i=0; i