{"id":963,"date":"2014-09-09T01:41:24","date_gmt":"2014-09-08T17:41:24","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=963"},"modified":"2014-09-09T02:47:17","modified_gmt":"2014-09-08T18:47:17","slug":"bestcoder-round-8","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bestcoder-round-8\/","title":{"rendered":"BestCoder Round #8"},"content":{"rendered":"

<\/p>\n

Problem xxx. ABC<\/h2>\n

Brief description:<\/h3>\n

…<\/p>\n

Analysis:<\/h3>\n

…<\/p>\n

External link:<\/h3>\n

Problem 1004. Primitive Roots <\/h2>\n

Brief description:<\/h3>\n

\u6c42 n \u7684\u6240\u6709\u539f\u6839\u3002<\/p>\n

Analysis:<\/h3>\n

…
\n\u6ce8\u610f\u5e38\u6570\u3002<\/p>\n

\r\nint getPrimitive(int n){\r\n    int p = phi[n]; VI d; for (int i=2;i*i<=p;++i) if (!(p%i)) d.PB(i), d.PB(p\/i);\r\n\r\n    bool fb = 1;\r\n\r\n    UNQ(d); MOD = n; FOR(i, 2, n) if (pow(i, p) == 1){\r\n        int j = 0; REP_N(j, SZ(d)) if (pow(i, d[j]) == 1) break;\r\n\r\n        if (j == SZ(d)){\r\n            if (!fb) putchar(' '); fb = 0;\r\n            cout << i;\r\n        }\r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n
\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int PMAX = 1000009;\r\nVI P; bitset<PMAX> isC; int phi[PMAX], min_p[PMAX];\r\n#define ii (i*P[j])\r\nvoid sieve(){\r\n    phi[1] = 1; FOR(i, 2, PMAX){\r\n        if (!isC[i]) P.PB(i),min_p[i]=i,phi[i]=i-1;\r\n        for (int j=0;j<SZ(P)&&ii<PMAX;++j){\r\n            isC[ii]=1,min_p[ii]=P[j]; if (i%P[j]==0){\r\n                phi[ii] = phi[i]*P[j];\r\n                break;\r\n            }\r\n            else{\r\n                phi[ii] = phi[i]*P[j]-phi[i];\r\n            }\r\n        }\r\n    }\r\n}\r\n#undef ii\r\n\r\n\r\nint getPrimitive(int n){\r\n    int p = phi[n]; VI d;\r\n    for (int i=2;i*i<=p;++i) if (p%i==0){\r\n        d.PB(i); do p\/=i;while(p%i==0);\r\n    }\r\n    if (p>1)d.PB(p);\r\n\r\n    p = phi[n]; MOD = n; FOR(i, 2, n) if (pow(i, p) == 1){\r\n        int j = 0; REP_N(j, SZ(d)) if (pow(i, p\/d[j]) == 1) break;\r\n        if (j == SZ(d)) return i;\r\n    }\r\n    return 0;\r\n}\r\n\r\n\r\nbool ck(int n){\r\n    if (n == 4) return 1;\r\n\tif(n%2==0)n\/=2;if(n%2==0) return 0;\r\n\tint p=min_p[n]; do n\/=p; while (n%p==0);\r\n\treturn n==1;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    sieve();\r\n\r\n    int n; while (~scanf("%d", &n)){\r\n        if (n <= 2) puts("1");\r\n        else if (!ck(n)) puts("-1");\r\n        else{\r\n            MOD = n; int g = getPrimitive(n), p = phi[n]; VI G;\r\n            REP_1(i, p\/2) if (gcd(i, p-i) == 1) G.PB(pow(g, i)),G.PB(pow(g, p-i));\r\n            UNQ(G); printf("%d", G[0]); FOR(i, 1, SZ(G)) printf(" %d", G[i]);\r\n            puts("");\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
\r\n#include <map>\r\n#include <set>\r\n#include <list>\r\n#include <cmath>\r\n#include <ctime>\r\n#include <deque>\r\n#include <queue>\r\n#include <stack>\r\n#include <bitset>\r\n#include <cctype>\r\n#include <cstdio>\r\n#include <string>\r\n#include <vector>\r\n#include <cassert>\r\n#include <cstdlib>\r\n#include <cstring>\r\n#include <iomanip>\r\n#include <sstream>\r\n#include <iostream>\r\n#include <algorithm>\r\n\r\nusing namespace std;\r\n\r\n#define PB push_back\r\n#define MP make_pair\r\n#define AA first\r\n#define BB second\r\n#define OP begin()\r\n#define ED end()\r\n#define SZ size()\r\n#define SORT(x) sort(x.OP,x.ED)\r\n#define SQ(x) ((x)*(x))\r\n#define SSP system("pause")\r\n#define cmin(x,y) x=min(x,y)\r\n#define cmax(x,y) x=max(x,y)\r\ntypedef long long LL;\r\ntypedef pair<int, int> PII;\r\nconst double eps=1e-8;\r\nconst double PI=acos(-1.);\r\nconst LL MOD = 1000000007;\r\nLL powMod(LL a,LL b,LL m) {\r\n\tLL ret=1;\r\n\twhile(b) {\r\n\t\tif(b&1)ret=ret*a%m;\r\n\t\ta=a*a%m;\r\n\t\tb>>=1;\r\n\t}\r\n\treturn ret;\r\n}\r\nint eulerPhi(int n) {\r\n\tint res = n;\r\n\tfor(int i = 2; i * i <= n; i++)\r\n\t\tif(n % i == 0) {\r\n\t\t\tres = res \/ i * (i - 1);\r\n\t\t\tfor(; n % i == 0; n \/= i);\r\n\t\t}\r\n\tif(n != 1) res = res \/ n * (n - 1);\r\n\treturn res;\r\n}\r\nint find_root(int P) {\r\n\tif(P==2)return 1;\r\n\tint Q=eulerPhi(P);\r\n\tint phi=Q;\r\n\tvector<int>G;\r\n\tint i,j;\r\n\tfor(i=2; i*i<=Q; i++)if(Q%i==0) {\r\n\t\t\tG.PB(i);\r\n\t\t\twhile(Q%i==0)Q\/=i;\r\n\t\t}\r\n\tif(Q>1)G.PB(Q);\r\n\tfor(i=2;; i++)if(powMod(i,phi,P)==1) {\r\n\t\t\tint flag=1;\r\n\t\t\tfor(j=0; j<G.SZ; j++)if(powMod(i,phi\/G[j],P)==1) {flag=0; break;}\r\n\t\t\tif(flag)return i;\r\n\t\t}\r\n\treturn -1;\r\n}\r\nbool check(int n) {\r\n\tvector<PII>L;\r\n\tint cnt=0;\r\n\twhile(n%2==0)n\/=2,cnt++;\r\n\tif(cnt>1)return 0;\r\n\tint i;\r\n\tfor(i=3; i*i<=n; i++)if(n%i==0)break;\r\n\tif(n%i==0) {\r\n\t\twhile(n%i==0)n\/=i;\r\n\t\tif(n>1)return 0;\r\n\t\treturn 1;\r\n\t}\r\n\treturn 1;\r\n}\r\nint __gcd(int a,int b) {\r\n\treturn b?__gcd(b,a%b):a;\r\n}\r\nint main() {\r\n\t\/\/freopen("","r",stdin);\r\n\t\/\/freopen("","w",stdout);\r\n\tint i,j,k,T;\r\n\tint n;\r\n\twhile(cin>>n) {\r\n\t\tif(n==1) {\r\n\t\t\tprintf("1\\n");\r\n\t\t\tcontinue;\r\n\t\t}\r\n\t\tif(n==2) {\r\n\t\t\tprintf("1\\n");\r\n\t\t\tcontinue;\r\n\t\t}\r\n\t\tif(n==4) {\r\n\t\t\tprintf("3\\n");\r\n\t\t\tcontinue;\r\n\t\t}\r\n\t\tif(!check(n)) {\r\n\t\t\tprintf("-1\\n");\r\n\t\t\tcontinue;\r\n\t\t}\r\n\t\tint __=find_root(n);\r\n\t\tint Q=eulerPhi(n);\r\n\t\tvector<int>L;\r\n\t\tfor(i=1; i+i<=Q; i++)if(__gcd(i,Q-i)==1) {\r\n\t\t\t\tL.PB(powMod(__,i,n));\r\n\t\t\t\tL.PB(powMod(__,Q-i,n));\r\n\t\t\t}\r\n\t\tsort(L.OP,L.ED);\r\n\t\tL.erase(unique(L.OP,L.ED),L.ED);\r\n\t\tprintf("%d",L[0]);\r\n\t\tfor(i=1; i<L.SZ; i++)printf(" %d",L[i]);\r\n\t\tprintf("\\n");\r\n\t}\r\n\treturn 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-963","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fx","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/963","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=963"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/963\/revisions"}],"predecessor-version":[{"id":964,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/963\/revisions\/964"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=963"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=963"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}