http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=3071<\/p>\n
\r\n#include \r\n#include \r\nusing namespace std;\r\nconst int P[] = {2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};\r\nconst int N = 205011, M = 35;\r\n\r\nint l[2*N-1], r[2*N-1];\r\nlong long gcd_key[2*N-1]; long long lcm_key[2*N-1];\r\nint left_child[2*N-1], right_child[2*N-1];\r\nint parent[2*N-1]; int total, root;\r\nint bottom[N]; int n, m;\r\nlong long num[N];\r\n\r\nint a, b ,c, p; long long gcd, lcm;\r\n\r\n\r\nlong long f(int a){\r\n long long x = 0, y = 1;\r\n for (int i=0;i<35;i++,y<<=1){\r\n if (a%P[i]==0){\r\n x|=y; a\/=P[i];\r\n }\r\n }\r\n return x;\r\n}\r\n\r\nint g(long long x){\r\n int a = 1; long long y = 1;\r\n for (int i=0;i<35;i++,y<<=1){\r\n if ((x&y)!=0){\r\n a = (a * P[i]) % p;\r\n x &=~ y;\r\n }\r\n }\r\n return a;\r\n}\r\n\r\n\r\n\r\nvoid updata(int now){\r\n gcd_key[now] = gcd_key[left_child[now]] & gcd_key[right_child[now]];\r\n lcm_key[now] = lcm_key[left_child[now]] | lcm_key[right_child[now]];\r\n}\r\n\r\nvoid query_gcd(int now){\r\n if (a<=l[now]&&r[now]<=b){\r\n gcd = gcd & gcd_key[now];\r\n return;\r\n }\r\n\r\n int m = (l[now]+r[now])\/2;\r\n if (a<=m) query_gcd(left_child[now]);\r\n if (m< b) query_gcd(right_child[now]);\r\n}\r\nvoid query_lcm(int now){\r\n if (a<=l[now]&&r[now]<=b){\r\n lcm = lcm | lcm_key[now];\r\n return;\r\n }\r\n\r\n int m = (l[now]+r[now])\/2;\r\n if (a<=m) query_lcm(left_child[now]);\r\n if (m< b) query_lcm(right_child[now]);\r\n}\r\n\r\nvoid modify(){\r\n int now = parent[bottom[a]];\r\n while (now!=-1){\r\n updata(now); now = parent[now];\r\n }\r\n}\r\n\r\n\r\nvoid build(int &now, int a, int b){\r\n now = total++;\r\n l[now] = a; r[now] = b;\r\n if (a==b){\r\n gcd_key[now] = lcm_key[now] = num[a];\r\n bottom[a] = now;\r\n }\r\n else {\r\n int m = (a+b)\/2;\r\n build(left_child[now],a ,m); build(right_child[now],m+1 ,b);\r\n parent[left_child[now]] = now; parent[right_child[now]] = now;\r\n updata(now);\r\n }\r\n}\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nvoid init(){\r\n int a;\r\n for (int i=1;i<=n;i++){\r\n scanf(\"%d\", &a); num[i] = f(a);\r\n }\r\n total = 0;\r\n build(root,1,n);\r\n}\r\n\r\n\r\n\r\nint main(){\r\n \/\/p = 100; cout << g(f(97)) << endl;\r\n parent[0] = -1; char ch;\r\n\r\n while(scanf(\"%d%d\",&n, &m) == 2){\r\n init();\r\n while (m--){\r\n scanf(\" %c\", &ch);\r\n switch(ch){\r\n case 'C':\r\n scanf(\"%d%d%d\",&a, &b);\r\n gcd_key[bottom[a]] = lcm_key[bottom[a]] = num[a] = f(b);\r\n modify();\r\n break;\r\n case 'G':\r\n scanf(\"%d%d%d\",&a ,&b, &p);gcd = num[a];\r\n query_gcd(root);\r\n printf(\"%d\\n\", g(gcd));\r\n break;\r\n case 'L':\r\n scanf(\"%d%d%d\",&a, &b, &p);lcm = num[a];\r\n query_lcm(root);\r\n printf(\"%d\\n\", g(lcm));\r\n }\r\n }\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=3071 #include #include using namespace std; const int P[] = {2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}; const int N = 205011, M = 35; int l[2*N-1], r[2*N-1]; long long gcd_key[2*N-1]; long long lcm_key[2*N-1]; int left_child[2*N-1], right_child[2*N-1]; int parent[2*N-1]; int total, root; int bottom[N]; int n, m; long long num[N]; int a, b ,c, p; long long gcd, lcm; long long […]<\/p>\n","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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-124","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-20","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/124","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=124"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/124\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=124"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=124"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=124"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}