2013-11-21 09:55:11      个评论

2 -- 24

2 -- 12

2 -- 6

3 （3是质数，结束）

[html]

120

5

ac代码

[cpp]

#include <stdio.h>

int main()

{

int n, count, i;

while (scanf("%d", &n) != EOF) {

count = 0;

for (i = 2; i * i <= n; i ++) {

if(n % i == 0) {

while (n % i == 0) {

count ++;

n /= i;

}

}

}

if (n  > 1) {

count ++;

}

printf("%d\n", count);

}

return 0;

}

[html]

6 10

1

a^k和n!都可能非常大，甚至超过long long int的表示范围，所以也就不能直接用取余操作判断它们之间是否存在整除关系，因此我们需要换一种思路，从分解质因数入手，假设两个数a和b：

a = p1^e1 * p2^e2 * ... * pn^en,  b = p1^d1 * p2^d2 * ... * pn^dn, 则b除以a可以表示为：

b / a = (p1^d1 * p2^d2 * ... * pn^dn) / (p1^e1 * p2^e2 * ... * pn^en)

[cpp]

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 1001

int prime[N], size;

/**

* 素数筛选法进行预处理

*/

void initProcess()

{

int i, j;

for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) {

prime[i] = 1;

}

size = 0;

for (i = 2; i < N; i ++) {

if (prime[i]) {

size ++;

for (j = 2 * i; j < N; j += i) {

prime[j] = 0;

}

}

}

}

int main(void)

{

int i, n, a, k, num, count, base, tmp, *ansbase, *ansnum;

// 预处理

initProcess();

while (scanf("%d %d", &n, &a) != EOF) {

ansbase = (int *)calloc(size, sizeof(int));

ansnum = (int *)calloc(size, sizeof(int));

// 将a分解质因数

for (i = 2, num = 0; i < N && a != 1; i ++) {

if (prime[i] && a % i == 0) {

ansbase[num] = i;

ansnum[num] = 0;

while (a != 1 && a % i == 0) {

ansnum[num] += 1;

a = a / i;

}

num ++;

}

}

// 求最小的k

for (i = 0, k = 0x7fffffff; i < num; i ++) {

base = ansbase[i];

count = 0;

while (base <= n) {

count += n / base;

base *= ansbase[i];

}

tmp = count / ansnum[i];

if (tmp < k) k = tmp;

}

printf("%d\n", k);

}

return 0;

}

/**************************************************************

Problem: 1104

User: wangzhengyi

Language: C

Result: Accepted

Time:0 ms

Memory:916 kb

****************************************************************/

n可以分解质因数：n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,

[html] view plaincopy

5

1 3 4 6 12

1

2

3

4

6

[cpp]

#include <stdio.h>

#include <stdlib.h>

#define N 40000

typedef long long int lint;

int prime[N], size;

void init()

{

int i, j;

for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) {

prime[i] = 1;

}

size = 0;

for (i = 2; i < N; i ++) {

if (prime[i]) {

size ++;

for (j = 2 * i; j < N; j += i)

prime[j] = 0;

}

}

}

lint numPrime(int n)

{

int i, num, *ansnum, *ansprime;

lint count;

ansnum = (int *)malloc(sizeof(int) * (size + 1));

ansprime = (int *)malloc(sizeof(int) * (size + 1));

for (i = 2, num = 0; i < N && n != 1; i ++) {

if (prime[i] && n % i == 0) {

ansprime[num] = i;

ansnum[num] = 0;

while (n != 1 && n % i == 0) {

ansnum[num] += 1;

n /= i;

}

num ++;

}

}

if (n != 1) {

ansprime[num] = n;

ansnum[num] = 1;

num ++;

}

for (i = 0, count = 1; i < num; i ++) {

count *= (ansnum[i] + 1);

}

free(ansnum);

free(ansprime);

return count;

}

int main(void)

{

int i, n, *arr;

lint count;

init();

while (scanf("%d", &n) != EOF && n != 0) {

arr = (int *)malloc(sizeof(int) * n);

for (i = 0; i < n; i ++) {

scanf("%d", arr + i);

}

for (i = 0; i < n; i ++) {

count = numPrime(arr[i]);

printf("%lld\n", count);

}

free(arr);

}

return 0;

}

/**************************************************************

Problem: 1087

User: wangzhengyi

Language: C

Result: Accepted

Time:190 ms

Memory:1068 kb

****************************************************************/