話說昨天做牛客三模題目，前面的筆試部分以及前兩道編程題很快做完了， 這是第三道“壓軸”題目。 業界話叫防AK。搞了 一個半小時，思路亂的像毛線一樣, 一看到素數就想到數論，費馬小定理，容斥原理，歐拉函數，，，想到這些就冷汗各種出。交完卷看題解，看了半天，愣是沒理解（好傷~~~）。
今天整理下思緒，稍微手動模擬幾個樣例。哦，原來是這樣~~~~， 還是俗話說的好啊 —— 靜心生慧。
題目描述
牛牛和羊羊在玩一個有趣的猜數游戲。在這個游戲中,牛牛玩家選擇一個正整數,羊羊根據已給的提示猜這個數字。第i個提示是"Y"或者"N",表示牛牛選擇的數是否是i的倍數。
例如,如果提示是"YYNYY",它表示這個數使1,2,4,5的倍數,但不是3的倍數。
注意到一些提示會出現錯誤。例如: 提示"NYYY"是錯誤的,因為所有的整數都是1的倍數,所以起始元素肯定不會是"N"。此外,例如"YNNY"的提示也是錯誤的,因為結果不可能是4的倍數但不是2的倍數。
現在給出一個整數n,表示已給的提示的長度。請計算出長度為n的合法的提示的個數。
例如 n = 5:
合法的提示有:
YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY
YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY
所以輸出12
輸入描述:
輸入包括一個整數n(1 ≤ n ≤ 10^6),表示已給提示的長度。
輸出描述:
輸出一個整數,表示合法的提示個數。因為答案可能會很大,所以輸出對于1000000007的模
輸入例子1:
5
輸出例子1:
12
思路分析
仔細分析我們可以發現一個位置是Y還是N依賴于他的倍數。
考慮若干個素數p0,p1,p2...p3,當他們的乘積那個數確定為Y,那么它們一定也是Y。
例如：
如果27是Y,那么9一定是Y,3也一定是Y,但是81可以是Y或者N。
由于每個數都可以分解為若干素數的乘積。于是我們考慮范圍內的素數及其k次冪的位置的情況,其他數字都可以由這些組合而來。
例如： n = 8, 考慮2的次冪：
- 如果 8 是 Y, 那么 4, 2 都是Y.
- 如果 8 是 N, 4 是 Y, 那么 2 是Y.
- 如果 8 是 N, 4 是 N, 2 是 Y 或是 N.
共 4 種情況. 推公式算出4 即：8 = 2^3, 3 + 1 = 4。3 之所以加 1 是因為最小的那個位置（例子中的2），最后可以為Y也可以為N.
然后完整的模擬 n = 6時：
先說結果怎么算： 2^2 <= 6 , 3^1 <= 6， 5 ^ 1 <= 6. （注意, 2，3，5都是小于6的素數）
n = 6時的總情況數為： (2+1)*(1+1)*(1+1) = 12.
上面的式子看上去好像只是確定了位置 2，4，3，5的擺放情況， 其實 1的也確定了，因為 1的位置永遠是 Y嘛。 6的位置怎么確定的呢？
哈哈， 由2，3完全確定了。 如果2 是Y, 3 是N， 那么 6一定是 N. 如果2 是Y, 3是 Y,那么6一定是Y(因為能整除2和3一定能整除6啊),,,
這樣結論就出來了： 只要確定了 <= n 的素數以及素數的冪的位置的擺放情況數，整個序列的擺放情況就確定了。
如 n = 12 時：
只要確定了 2, 4, 8; 3, 9; 5; 7; 11;的擺放情況，那么 1->12的擺放情況就都確定了。6 由 2,3確定； 10 由 2, 5確定； 12 由 3, 4確定。
因為: 2^3 <= 12; 3^2 <= 12; 5^1 <= 12; 7^1 <= 12; 11^1 <= 12;
總情況數即為： (3+1) * (2+1) * (1+1)*(1+1)*(1+1) = 96.
代碼:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
// #include <unordered_set>
// #include <unordered_map>
#include <algorithm>
#include <stdexcept>
using namespace std;
const int maxn = 10e6 + 5;
const int mod = 1e9 + 7;
bool visited[maxn];
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
long long ans = 1;
memset(visited, 0, sizeof(visited));
for(int i = 2; i <= n; i++)
{
if(visited[i])
continue;
for(int j = i + i; j <= n; j += i)
visited[j] = true;
int tmp = n;
int cnt = 0;
while(tmp >= i)
{
tmp /= i;
cnt++;
}
ans = ans * (cnt + 1) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
文章列表
留言列表
