首页 > 代码库 > POJ 1091 跳蚤
POJ 1091 跳蚤
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 9914 | Accepted: 3032 |
Description
Z 城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤 发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S， 然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
Input
两个整数N和M(N <= 15 , M <= 100000000)。
Output
可以完成任务的卡片数。
Sample Input
2 4
Sample Output
12
用到素因子分解，高精度，以及集合中的互斥原理。代码如下：
1 #include <stdio.h> 2 3 long long factor[10000000]; 4 long long factor_num = 0; 5 6 long long M; 7 long long N; 8 9 10 void get_factor(long long num, long long factor[], long long *factor_num)11 {12 *factor_num = 0;13 for (long long i = 2; i * i <= num ; i++)14 {15 if (num %i == 0)16 {17 *factor_num = (*factor_num) + 1;18 factor[*factor_num] = i;19 while( num % i == 0)20 {21 num = num / i;22 }23 }24 }25 if(num > 1)26 {27 *factor_num = (*factor_num) + 1;28 factor[*factor_num] = num;29 }30 }31 32 33 long long pow(long long x, long long index)34 {35 long long result = 1;36 for (long long i = 1; i <= index; i++)37 {38 result *= x;39 }40 return result;41 }42 43 44 45 int main(int argc, char * argv[])46 {47 48 scanf("%lld", &N);49 scanf("%lld", &M);50 51 //printf("N=%d M=%ld\n", N, M);52 53 long long total = pow(M, N);54 get_factor(M, factor, &factor_num);55 56 //printf("total=%ld\n", total);57 58 59 unsigned long long bi_factor_num = (1 << factor_num);60 //printf("bi_factor_num=%d\n", bi_factor_num);61 62 63 for (unsigned long long i = 1; i < bi_factor_num; i++)64 {65 //printf("%d-----\n", i);66 long long t = 0;67 long long facts = 1;68 long long k = 1;69 for (unsigned long long j = i; j >= 1; j = j >> 1)70 {71 if (j & 1)72 {73 t++;74 facts *= factor[k];75 }76 k++;77 //printf("j =%d\n", j);78 //printf("k =%d\n", k);79 }80 //printf("facts = %d %d %d\n", facts, t, pow(M/facts, N));81 if (t % 2 == 1)82 {83 total = total - pow(M/facts, N);84 }85 else if (t % 2 == 0)86 {87 total = total + pow(M/facts, N);88 }89 90 }91 92 //printf("Done\n");93 printf("%lld\n", total);94 return 0;95 }
POJ 1091 跳蚤
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。