{"problem":{"name":"「Cfz Round 3」Xor with Gcd","description":{"content":"给定一个整数 $n$。 你需要求出 $\\bigoplus\\limits_{i=1}^{n} \\gcd(i,n)$，即 $\\gcd(1,n) \\oplus \\gcd(2,n) \\oplus \\cdots \\oplus \\gcd(n,n)$ 的值。其中 $\\gcd(a,b)$ 表示 $a$ 和 $b$ 的**最大公约数**，$\\bigoplus$ 表示**按位异或**，即 C++ 中的 `^`。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10031"},"statements":[{"statement_type":"Markdown","content":"给定一个整数 $n$。\n\n你需要求出 $\\bigoplus\\limits_{i=1}^{n} \\gcd(i,n)$，即 $\\gcd(1,n) \\oplus \\gcd(2,n) \\oplus \\cdots \\oplus \\gcd(n,n)$ 的值。其中 $\\gcd(a,b)$ 表示 $a$ 和 $b$ 的**最大公约数**，$\\bigoplus$ 表示**按位异或**，即 C++ 中的 `^`。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据，输入一行一个整数 $n$。\n\n## Output\n\n对于每组测试数据，输出一行一个整数，表示 $\\bigoplus\\limits_{i=1}^{n} \\gcd(i,n)$ 的值。\n\n[samples]\n\n## Background\n\n她是午夜潜入海风漂流的沙砾\n\n极光与她一齐许下明日愿景\n\n飞身电波铺满天穹而海仍平静\n\n“愿世界都繁花似锦”\n\n## Note\n\n#### 「样例解释 #1」\n\n对于第 $1$ 组数据，$\\bigoplus\\limits_{i=1}^{2} \\gcd(i,2)=\\gcd(1,2)\\oplus\\gcd(2,2)=1\\oplus2=3$。\n\n对于第 $2$ 组数据，$\\bigoplus\\limits_{i=1}^{3} \\gcd(i,3)=\\gcd(1,3)\\oplus\\gcd(2,3)\\oplus\\gcd(3,3)=1\\oplus1\\oplus3=3$。\n\n#### 「数据范围」\n\n对于所有数据，$1 \\le T \\le 100$，$1 \\le n \\le 10^{18}$。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10031","tags":["数学","洛谷原创","O2优化","最大公约数 gcd","洛谷月赛","Ad-hoc"],"sample_group":[["3\n2\n3\n6\n","3\n3\n5"]],"created_at":"2026-03-03 11:09:25"}}