实际数

大家好，欢迎来到IT知识分享网。

题目：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1416

题意：给一个数，其中，判断是不是实际数。实际数的定义如下：

     对于一个数，如果区间的每一个数都能用的某些因子的和来表示，那么称是实际数，否则不是。

     例如：12是实际数，因为它的所有因子为1，2，3，4，6，而5 = 2 + 3，7 = 3 + 4，8 = 2 + 6，

     9 = 3 + 6，10 = 1 + 3 + 6，11 = 2 + 3 + 6。

分析：本题有一个很好的结论。描述如下：

     先把素因子分解得到，且，为实际数当且仅当，且对于2到之

     间的每一个满足条件

代码：

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <bitset> using namespace std; const int N = ; typedef long long LL; bitset<N> prime; int p[N]; int cnt; void isprime() { cnt = 0; prime.set(); for(int i=2; i<N; i++) { if(prime[i]) { p[cnt++] = i; for(int j=i+i; j<N; j+=i) prime[j] = false; } } } bool OK(LL n) { if(n == 1) return 1; if(n % 2) return 0; LL ans = 2; while(n % 2 == 0) { ans *= 2; n >>= 1; } ans--; for(int i=1; i<cnt&&p[i]<=n; i++) { if(n%p[i]==0) { if(p[i] > ans + 1) return 0; LL tmp = p[i]; while(n%p[i]==0) { tmp *= p[i]; n /= p[i]; } tmp--; tmp /= (p[i] - 1); ans *= tmp; if(ans >= n) return 1; } } if(n > ans + 1) return 0; return 1; } int main() { LL n; int T; isprime(); scanf("%d",&T); while(T--) { scanf("%lld",&n); if(OK(n)) puts("Yes"); else puts("No"); } return 0; }