{"id":5198,"date":"2024-09-25T10:01:05","date_gmt":"2024-09-25T02:01:05","guid":{"rendered":""},"modified":"2024-09-25T10:01:05","modified_gmt":"2024-09-25T02:01:05","slug":"\u6570\u5b57\u903b\u8f91\u57fa\u7840\u4e0everilog\u8bbe\u8ba1\u7b54\u6848_\u6570\u8bba\u4e2d\u672a\u89e3\u51b3\u7684\u95ee\u9898","status":"publish","type":"post","link":"https:\/\/mushiming.com\/5198.html","title":{"rendered":"\u6570\u5b57\u903b\u8f91\u57fa\u7840\u4e0everilog\u8bbe\u8ba1\u7b54\u6848_\u6570\u8bba\u4e2d\u672a\u89e3\u51b3\u7684\u95ee\u9898"},"content":{"rendered":"

\n <\/path> \n<\/svg> <\/p>\n

\u9898\u76ee\u94fe\u63a5
Problem Description
Multiple query, for each n, you need to get
n i-1
\u2211 \u2211 [gcd(i + j, i - j) = 1]
i=1 j=1<\/p>\n

Input
On the first line, there is a positive integer T, which describe the number of queries. Next there are T lines, each line give a positive integer n, as mentioned above.
T<=1e5, n<=2e7<\/p>\n

Output
Your output should include T lines, for each line, output the answer for the corre- sponding n.<\/p>\n

Sample Input
4
978
438
233
666<\/p>\n

Sample Output<\/p>\n

38951
11065
89963<\/p>\n

Source
2018 Multi-University Training Contest 10
\u601d\u8def\uff1a\"\u6570\u5b57\u903b\u8f91\u57fa\u7840\u4e0everilog\u8bbe\u8ba1\u7b54\u6848_\u6570\u8bba\u4e2d\u672a\u89e3\u51b3\u7684\u95ee\u9898
\u53d8\u6362\u5dee\u4e0d\u591a\u5c31\u662f\u8fd9\u6837\uff0c\u4e8e\u662f\u5bf9\u4e8e\u6bcf\u4e00\u4e2ai\u5c31\u53d8\u6210\u4e86\u6c422i\u7684\u6b27\u62c9\u51fd\u6570\u96642\u4e86\uff0c\u6c42\u4e00\u4e0b\u524d\u7f00\u548c\u5c31\u884c\u3002<\/p>\n

#include<\/span><bits\/stdc++.h><\/span><\/span> using<\/span> namespace<\/span> std;<\/span> typedef<\/span> long<\/span> long<\/span> ll;<\/span> const<\/span> int<\/span> N=<\/span>2e7<\/span>+<\/span>5<\/span>;<\/span> ll euler[<\/span>N<<<\/span>1<\/span>]<\/span>,<\/span>sum[<\/span>N]<\/span>,<\/span>prim[<\/span>N<<<\/span>1<\/span>]<\/span>;<\/span> void<\/span> get_euler<\/span>(<\/span>int<\/span> n)<\/span>{ \n   <\/span> \/\/\u6b27\u62c9\u51fd\u6570 <\/span> memset<\/span>(<\/span>euler,<\/span> 0<\/span>,<\/span> sizeof<\/span> euler)<\/span>;<\/span> euler[<\/span>1<\/span>]<\/span> =<\/span> 1<\/span>;<\/span> int<\/span> id =<\/span> 0<\/span>;<\/span> for<\/span>(<\/span>int<\/span> i =<\/span> 2<\/span>;<\/span> i <<\/span> n;<\/span> ++<\/span>i)<\/span> { \n   <\/span> if<\/span>(<\/span>!<\/span>euler[<\/span>i]<\/span>)<\/span> { \n   <\/span> euler[<\/span>i]<\/span> =<\/span> i -<\/span> 1<\/span>;<\/span> prim[<\/span>id++<\/span>]<\/span> =<\/span> i;<\/span> }<\/span> for<\/span>(<\/span>int<\/span> j =<\/span> 0<\/span>;<\/span> j <<\/span> id &&<\/span> prim[<\/span>j]<\/span>*<\/span>i <<\/span>n;<\/span> ++<\/span>j)<\/span> { \n   <\/span> if<\/span>(<\/span>i %<\/span> prim[<\/span>j]<\/span>)<\/span> { \n   <\/span> euler[<\/span>i*<\/span>prim[<\/span>j]<\/span>]<\/span> =<\/span> euler[<\/span>i]<\/span> *<\/span> (<\/span>prim[<\/span>j]<\/span>-<\/span>1<\/span>)<\/span>;<\/span> }<\/span> else<\/span> { \n   <\/span> euler[<\/span>i*<\/span>prim[<\/span>j]<\/span>]<\/span> =<\/span> euler[<\/span>i]<\/span> *<\/span> prim[<\/span>j]<\/span>;<\/span> break<\/span>;<\/span> }<\/span> }<\/span> }<\/span> }<\/span> int<\/span> main<\/span>(<\/span>)<\/span> { \n   <\/span> int<\/span> n,<\/span>T;<\/span> get_euler<\/span>(<\/span>N<<<\/span>1<\/span>)<\/span>;<\/span> sum[<\/span>1<\/span>]<\/span>=<\/span>0<\/span>;<\/span> for<\/span>(<\/span>int<\/span> i=<\/span>2<\/span>;<\/span>i<=<\/span>N;<\/span>++<\/span>i)<\/span> sum[<\/span>i]<\/span>=<\/span>euler[<\/span>2<\/span>*<\/span>i]<\/span>\/<\/span>2<\/span>,<\/span>sum[<\/span>i]<\/span>+<\/span>=<\/span>sum[<\/span>i-<\/span>1<\/span>]<\/span>;<\/span> scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>T)<\/span>;<\/span> while<\/span>(<\/span>T--<\/span>)<\/span> { \n   <\/span> scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>n)<\/span>;<\/span> printf<\/span>(<\/span>\"%lld\\n\"<\/span>,<\/span>sum[<\/span>n]<\/span>)<\/span>;<\/span> }<\/span> }<\/span> <\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u6570\u5b57\u903b\u8f91\u57fa\u7840\u4e0everilog\u8bbe\u8ba1\u7b54\u6848_\u6570\u8bba\u4e2d\u672a\u89e3\u51b3\u7684\u95ee\u9898\u9898\u76ee\u94fe\u63a5ProblemDescriptionMultiplequery,foreachn,youneedtogetni-1\u2211\u2211[g...","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/5198"}],"collection":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/comments?post=5198"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/5198\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=5198"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=5198"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=5198"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}