題目：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 = 1000005; 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; }

?

?

?

?

總結

以上是生活随笔為你收集整理的实际数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。