\u8fd9\u662f GESP 2024\u5e749\u6708 \u7684\u4e00\u9053\u679a\u4e3e\u9898\u3002\u9898\u76ee\u672c\u8eab\u4e0d\u96be，\u4f46\u6709\u51e0\u4e2a\u5730\u65b9\u7279\u522b\u5bb9\u6613\u51fa\u9519，\u6211\u628a\u8e29\u8fc7\u7684\u5751\u90fd\u5199\u51fa\u6765，\u5e0c\u671b\u80fd\u5e2e\u521a\u5b66\u5230\u8fd9\u91cc\u7684\u670b\u53cb\u5c11\u8d70\u5f2f\u8def\u3002<\/p>\n
\u9898\u76ee\u6765\u6e90：ACGO A75460 ｜ 2024\u5e749\u6708 \u4e94\u7ea7\u8d5b\u4e8b\u573a\u6b21：2024\u5e749\u6708 \u4e94\u7ea7<\/p>\n
\u9898\u76ee\u540d\u79f0：\u6311\u6218\u602a\u7269<\/p>\n
\u8d5b\u4e8b\u573a\u6b21：2024\u5e749\u6708 \u4e94\u7ea7<\/p>\n
\u96be\u5ea6\u5b9a\u4f4d：\u4e94\u7ea7<\/p>\n
\u6d89\u53ca\u77e5\u8bc6\u70b9：\u8d2a\u5fc3 \u6570\u8bba \u679a\u4e3e<\/p>\n
\u9898\u76ee\u94fe\u63a5：https:\/\/www.acgo.cn\/problemset\/info\/75460<\/p>\n
\u5c0f\u6768\u6b63\u5728\u548c\u4e00\u4e2a\u602a\u7269\u6218\u6597，\u602a\u7269\u7684\u8840\u91cf\u4e3a h，\u53ea\u6709\u5f53\u602a\u7269\u7684\u8840\u91cf\u6070\u597d\u4e3a 0 \u65f6\u5c0f\u6768\u624d\u80fd\u591f\u6210\u529f\u51fb\u8d25\u602a\u7269\u3002<\/p>\n
\u5c0f\u6768\u6709\u4e24\u79cd\u653b\u51fb\u602a\u7269\u7684\u65b9\u5f0f：<\/p>\n
\u5c0f\u6768\u60f3\u77e5\u9053\u81ea\u5df1\u80fd\u5426\u51fb\u8d25\u602a\u7269，\u5982\u679c\u80fd，\u5c0f\u6768\u60f3\u77e5\u9053\u81ea\u5df1\u6700\u5c11\u9700\u8981\u591a\u5c11\u6b21\u653b\u51fb\u3002<\/p>\n
\u8fd9\u9053\u9898\u7528\u5230\u7684\u524d\u7f6e\u77e5\u8bc6\u4e0d\u591a，\u6211\u4eec\u5148\u628a\u5b83\u8865\u9f50，\u5373\u4f7f\u4f60\u521a\u5b66\u5230\u8fd9\u91cc\u4e5f\u80fd\u770b\u61c2\u3002<\/p>\n
\u679a\u4e3e\u7684\u601d\u8def：\u628a\u6240\u6709\u53ef\u80fd\u7684\u60c5\u51b5\u9010\u4e2a\u8bd5\u4e00\u904d，\u5728\u6570\u636e\u8303\u56f4\u5141\u8bb8\u7684\u524d\u63d0\u4e0b，\u8fd9\u662f\u6700\u7a33\u59a5\u7684\u505a\u6cd5\u3002\u5173\u952e\u662f\u786e\u5b9a\u679a\u4e3e\u7684\u8303\u56f4\u548c\u987a\u5e8f，\u907f\u514d\u91cd\u590d\u6216\u6f0f\u89e3\u3002<\/p>\n
\u5148\u770b\u6e05\u695a\u9898\u76ee\u8981\u6211\u4eec\u505a\u4ec0\u4e48<\/p>\n
\u628a\u9898\u76ee\u8bfb\u4e24\u904d，\u6211\u4eec\u63d0\u53d6\u51fa\u5173\u952e\u4fe1\u606f：\u8f93\u5165\u662f\u4ec0\u4e48\u3001\u8981\u8f93\u51fa\u4ec0\u4e48\u3001\u6709\u54ea\u4e9b\u7ea6\u675f\u6761\u4ef6\u3002\u8fd9\u9053\u9898\u8003\u67e5\u7684\u662f\u679a\u4e3e，\u5c5e\u4e8e\u8fd9\u7c7b\u9898\u91cc\u6bd4\u8f83\u57fa\u7840\u7684\u4e00\u9053，\u628a\u9898\u76ee\u8981\u6c42\u4e00\u6b65\u6b65\u7ffb\u8bd1\u6210\u4ee3\u7801\u903b\u8f91\u5c31\u80fd\u89e3\u51b3\u3002<\/p>\n
\u6211\u7684\u601d\u8003\u8fc7\u7a0b<\/p>\n
\u8bfb\u5b8c\u9898\u4e4b\u540e，\u6211\u7684\u7b2c\u4e00\u53cd\u5e94\u662f\u8fd9\u6837\u7684：\u6311\u6218\u602a\u7269：\u7269\u7406\u653b\u51fb\u7b2c i \u6b21\u9020\u6210 2\u2071-1 \u4f24\u5bb3，\u9b54\u6cd5\u81f3\u591a\u4e00\u6b21\u9020\u6210\u4efb\u610f\u8d28\u6570\u4f24\u5bb3\u3002\u89c2\u5bdf\u5230 2\u2071-1 \u7684\u4e8c\u8fdb\u5236\u5168\u4e3a 1，\u7528\u82e5\u5e72\u6b21\u7269\u7406\u653b\u51fb\u53ef\u51d1\u51fa\u4efb\u610f\u300c\u8fde\u7eed\u4f4e\u4f4d 1\u300d\u7684\u6570，\u5269\u4f59\u90e8\u5206\u9700\u7528\u4e00\u6b21\u8d28\u6570\u9b54\u6cd5\u8865\u8db3，\u6545\u679a\u4e3e\u7269\u7406\u653b\u51fb\u6b21\u6570\u5e76\u5224\u65ad\u5269\u4f59\u662f\u5426\u4e3a\u8d28\u6570\u3002<\/p>\n
\u9700\u8981\u8bf4\u660e\u7684\u662f，\u4e0a\u9762\u8fd9\u4e2a\u601d\u8def\u662f\u628a\u9898\u76ee\u8981\u6c42\u76f4\u8bd1\u6210\u4ee3\u7801\u5f97\u5230\u7684，\u6ca1\u6709\u7528\u5230\u4ec0\u4e48\u9ad8\u7ea7\u6280\u5de7\u3002\u5bf9\u4e8e\u8fd9\u7c7b\u57fa\u7840\u9898，\u8bfb\u51c6\u9898\u610f\u52a0\u5199\u5bf9\u8fb9\u754c\u6bd4\u8ffd\u6c42\u5de7\u5999\u89e3\u6cd5\u66f4\u91cd\u8981，\u56e0\u4e3a\u8003\u8bd5\u91cc\u8fd9\u79cd\u9898\u662f\u5fc5\u987b\u62ff\u6ee1\u5206\u7684\u3002<\/p>\n
#include <bits\/stdc++.h>
\nusing namespace std;
\nvector<int> prime;
\nbool is_prime[100010];
\nvoid Eratosthenes(int n) {
\nis_prime[0] = is_prime[1] = false;
\nfor (int i = 2; i <= n; ++i) is_prime[i] = true; \/\/ \u904d\u5386
\nfor (int i = 2; i <= n; ++i) { \/\/ \u904d\u5386
\nif (is_prime[i]) { \/\/ \u5224\u65ad
\nprime.push_back(i);
\nif ((long long)i * i > n) continue; \/\/ \u5224\u65ad
\nfor (int j = i * i; j <= n; j += i) \/\/ \u904d\u5386
\nis_prime[j] = false;
\n}
\n}
\n}
\nint main() {
\nEratosthenes(100000);
\nint t;
\ncin>>t; \/\/ \u8bfb\u5165
\nwhile(t–){
\nint tmp=1;
\nint x;
\ncin>>x; \/\/ \u8bfb\u5165
\nint ans=0; \/\/ \u521d\u59cb\u5316
\nwhile(1){
\nif(is_prime[x]){ \/\/ \u5224\u65ad
\nans++;
\nbreak;
\n}
\nx-=tmp;
\nans++;
\nif(x<=0){ \/\/ \u5224\u65ad
\nif(x<0)ans=-1; \/\/ \u5224\u65ad
\nbreak;
\n}
\ntmp*=2;
\n}
\ncout<<ans<<"\\\\n"; \/\/ \u8f93\u51fa
\n}
\n}<\/p>\n
\u4e3a\u4e86\u770b\u5f97\u66f4\u6e05\u695a，\u6211\u4eec\u628a\u4ee3\u7801\u6309\u529f\u80fd\u5206\u6210\u51e0\u6bb5\u89e3\u91ca\u3002<\/p>\n
\u7b2c\u4e00\u6b65：\u5f15\u5165\u5934\u6587\u4ef6<\/p>\n
#include <bits\/stdc++.h>
\nusing namespace std;<\/p>\n
#include <iostream> \u63d0\u4f9b\u8f93\u5165\u8f93\u51fa\u529f\u80fd，using namespace std; \u8ba9\u6211\u4eec\u80fd\u76f4\u63a5\u5199 cin\u3001cout \u800c\u4e0d\u7528\u52a0\u524d\u7f00\u3002\u8fd9\u4e24\u884c\u662f\u51e0\u4e4e\u6240\u6709 C++ \u7a0b\u5e8f\u7684\u5f00\u5934，\u7167\u5199\u5373\u53ef\u3002<\/p>\n
\u7b2c\u4e8c\u6b65：\u8bfb\u5165\u6570\u636e<\/p>\n
cin>>t;
\ncin>>x;<\/p>\n
\u6ce8\u610f\u53d8\u91cf\u7684\u7c7b\u578b\u8981\u80fd\u88c5\u4e0b\u9898\u76ee\u7684\u6570\u636e\u3002\u6570\u636e\u53ef\u80fd\u8d85\u8fc7 21 \u4ebf\u65f6\u8981\u6539\u7528 long long\u3002<\/p>\n
\u7b2c\u4e09\u6b65：\u6838\u5fc3\u5904\u7406\u903b\u8f91<\/p>\n
for (int i = 2; i <= n; ++i) is_prime[i] = true;
\nfor (int i = 2; i <= n; ++i) {
\nfor (int j = i * i; j <= n; j += i)
\nwhile(t–){<\/p>\n
\u8fd9\u4e00\u6bb5\u662f\u6574\u9053\u9898\u7684\u5173\u952e，\u4e5f\u662f\u679a\u4e3e\u7684\u4f53\u73b0\u3002\u770b\u5faa\u73af\u7684\u4e09\u4e2a\u8981\u7d20：\u4ece\u54ea\u91cc\u5f00\u59cb\u3001\u4ec0\u4e48\u65f6\u5019\u7ed3\u675f\u3001\u6bcf\u6b21\u600e\u4e48\u53d8\u5316\u3002\u8fd9\u4e09\u4e2a\u8981\u7d20\u4efb\u4f55\u4e00\u4e2a\u5199\u9519，\u7ed3\u679c\u90fd\u4f1a\u4e0d\u5bf9\u3002<\/p>\n
\u7b2c\u56db\u6b65：\u6309\u8981\u6c42\u8f93\u51fa<\/p>\n
cout<<ans<<"\\\\n";<\/p>\n
\u8f93\u51fa\u683c\u5f0f\u5fc5\u987b\u548c\u9898\u76ee\u8981\u6c42\u7684\u5b8c\u5168\u4e00\u81f4\u3002\u5f88\u591a\u540c\u5b66\u7b97\u6cd5\u5b8c\u5168\u6b63\u786e\u5374\u56e0\u4e3a\u5c11\u4e86\u4e00\u4e2a\u6362\u884c\u6216\u8005\u7a7a\u683c\u591a\u5be1\u4e0d\u5bf9\u800c WA，\u8fd9\u79cd\u5206\u4e22\u5f97\u6700\u53ef\u60dc\u3002<\/p>\n
\u5149\u770b\u4ee3\u7801\u53ef\u80fd\u8fd8\u4e0d\u591f\u76f4\u89c2，\u6211\u4eec\u7528\u9898\u76ee\u7684\u6837\u4f8b\u5b9e\u9645\u8dd1\u4e00\u904d，\u770b\u770b\u7a0b\u5e8f\u662f\u600e\u4e48\u8d70\u7684\u3002<\/p>\n
\u4ee5\u9898\u76ee\u7684\u7b2c\u4e00\u7ec4\u6837\u4f8b\u4e3a\u4f8b：<\/p>\n
\u6837\u4f8b\u8f93\u5165<\/p>\n
3
\n6
\n188
\n9999<\/p>\n
\u6837\u4f8b\u8f93\u51fa<\/p>\n
2
\n4
\n-1<\/p>\n
\u628a\u8fd9\u4efd\u8f93\u5165\u4ee3\u8fdb\u4ee3\u7801，\u7a0b\u5e8f\u4f1a\u5148\u628a\u6570\u636e\u4f9d\u6b21\u8bfb\u5165，\u7136\u540e\u8fdb\u5165\u5faa\u73af\u9010\u4e2a\u5224\u65ad，\u628a\u6ee1\u8db3\u6761\u4ef6\u7684\u503c\u7d2f\u79ef\u8d77\u6765，\u6700\u540e\u6309\u683c\u5f0f\u8f93\u51fa\u3002\u5efa\u8bae\u4f60\u5bf9\u7167\u7740\u4ee3\u7801\u5728\u7eb8\u4e0a\u8d70\u4e00\u904d\u524d\u4e24\u6b21\u5faa\u73af，\u786e\u8ba4\u81ea\u5df1\u5bf9\u6bcf\u4e00\u6b65\u7684\u7406\u89e3\u90fd\u548c\u7a0b\u5e8f\u4e00\u81f4\u3002<\/p>\n
\u4e0b\u9762\u662f\u505a\u8fd9\u9053\u9898\u65f6\u6700\u5bb9\u6613\u51fa\u9519\u7684\u5730\u65b9，\u5bf9\u7167\u81ea\u5df1\u7684\u4ee3\u7801\u68c0\u67e5\u4e00\u4e0b：<\/p>\n
\u6700\u540e\u603b\u7ed3\u4e00\u4e0b\u8fd9\u9053\u9898\u5e26\u7ed9\u6211\u4eec\u7684\u901a\u7528\u7ecf\u9a8c：<\/p>\n
\u5982\u679c\u4f60\u5df2\u7ecf\u638c\u63e1\u679a\u4e3e\u7684\u57fa\u672c\u5199\u6cd5，\u8fd9\u9053\u9898\u53ef\u4ee5\u7528\u6765\u5de9\u56fa\u624b\u611f\u3002<\/p>\n
\u5982\u679c\u8fd9\u7bc7\u9898\u89e3\u5bf9\u4f60\u6709\u5e2e\u52a9，\u6b22\u8fce\u70b9\u8d5e\u6536\u85cf\u3002\u540e\u7eed\u6211\u4f1a\u7ee7\u7eed\u6309\u573a\u6b21\u6574\u7406 2024\u5e749\u6708 \u4e94\u7ea7 \u7684\u771f\u9898，\u5173\u6ce8\u6211\u53ef\u4ee5\u7b2c\u4e00\u65f6\u95f4\u770b\u5230\u66f4\u65b0\u3002\u6709\u66f4\u597d\u7684\u5199\u6cd5\u4e5f\u6b22\u8fce\u5728\u8bc4\u8bba\u533a\u4ea4\u6d41\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u662f GESP 2024\u5e749\u6708 \u7684\u4e00\u9053\u679a\u4e3e\u9898\u3002\u9898\u76ee\u672c\u8eab\u4e0d\u96be，\u4f46\u6709\u51e0\u4e2a\u5730\u65b9\u7279\u522b\u5bb9\u6613\u51fa\u9519，\u6211\u628a\u8e29\u8fc7\u7684\u5751\u90fd\u5199\u51fa\u6765，\u5e0c\u671b\u80fd\u5e2e\u521a\u5b66\u5230\u8fd9\u91cc\u7684\u670b\u53cb\u5c11\u8d70\u5f2f\u8def\u3002
\n\u9898\u76ee\u6765\u6e90：ACGO A75460 ｜ 2024\u5e749\u6708 \u4e94\u7ea7\u8d5b\u4e8b\u573a\u6b21：2024\u5e749\u6708 \u4e94\u7ea7
\n\u4e00\u3001\u9898\u76ee\u4fe1\u606f
\n\u9898\u76ee\u540d\u79f0：\u6311\u6218\u602a\u7269
\n\u8d5b\u4e8b\u573a\u6b21：2024\u5e749\u6708 \u4e94\u7ea7
\n\u96be\u5ea6\u5b9a\u4f4d：\u4e94\u7ea7
\n\u6d89\u53ca\u77e5\u8bc6\u70b9：\u8d2a\u5fc3 \u6570\u8bba <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[13413,13414,55,5181,4651],"topic":[],"class_list":["post-118145","post","type-post","status-publish","format-standard","hentry","category-server","tag-13413","tag-13414","tag-c","tag-gesp","tag-4651"],"yoast_head":"\n