\u5bb9\u65a5\u539f\u7406<\/p>\n
\u9898\u610f\u5f88\u7b80\u5355\uff0c\u5bb9\u6613\u63a8\u51fa\uff0c\u8981\u6c42\uff1a\u5c0f\u4e8e m \u7684\u6570\u4e2d\uff0c\u80fd\u591f\u88ab \u6bcf\u4e2a\u9752\u86d9\u6b65\u8ddd\u4e0em\u7684gcd \u6574\u9664\u7684\u6570\u7684\u548c\uff0c<\/p>\n
\u6309\u6700\u57fa\u7840\u7684\u5b66\u4e60\u7684\u5bb9\u65a5\u539f\u7406\u7684\u8bdd\uff0c \u96be\u4ee5\u89e3\u51b3\uff1b<\/p>\n
\u6240\u4ee5\u6709\u4e86\u4ee5\u4e0b\u4ee3\u7801\u7684\u89e3\u6cd5\uff1a<\/p>\n
\u9996\u5148\u627e\u5230 m \u7684\u6240\u6709\u56e0\u5b50\uff0c\u56e0\u4e3a\u53ea\u6709\u8fd9\u4e9b\u56e0\u5b50\u624d\u662f \u53ef\u80fd\u4f1a\u51fa\u73b0\u91cd\u590d\u7684\u70b9\uff0c\u4e5f\u662f\u9700\u8981\u6211\u4eec\u8fdb\u884c\u5bb9\u65a5\u7684\u5730\u65b9<\/p>\n
\u521d\u59cb num \u6570\u7ec4\u4e3a\u96f6\uff0c\u7528 vis \u6570\u7ec4\u4fdd\u5b58\u80fd\u88ab \u67d0\u4e2a\u9752\u86d9\u7684gcd \u6574\u9664\u7684\u56e0\u6570\uff0c\u7136\u540e\u627e num \u548c vis \u662f\u4e0d\u662f\u76f8\u7b49\uff0c<\/p>\n
\u5982\u679c\u4e0d\u76f8\u7b49\uff0c\u90a3\u4e48\u8fd9\u4e2a\u56e0\u5b50\u5c31\u662f\u4f5c\u4e3a\u4e00\u4e2a\u5bf9 \u7b54\u6848\u8fdb\u884c\u8d21\u732e\u7684 \u57fa\u7840\u5143\uff08\u610f\u601d\u5c31\u662f\uff0c\u8fd9\u4e2a\u6570\u7684\u6240\u6709\u500d\u6570\u4f1a\u5bf9\u7b54\u6848\u505a\u51fa\u8d21\u732e\uff09\uff0c\u540c\u65f6\u5bf9\u540e\u9762\u4ed6\u7684\u500d\u6570\u8fdb\u884c\u5904\u7406\uff0c\uff0c<\/p>\n
\u8fd9\u4e2a \u8d21\u732e\u503c \u4e5f\u5c31\u662f\uff08vis - num\uff09\uff0c\u8868\u793a\u91cd\u590d\u4e86\u591a\u52a0\u8fc7\u7684\u6b21\u6570\uff0c\u6216\u8005\u51cf\u591a\u4e86\u7684\u6b21\u6570<\/p>\n
<\/p>\n
\u5efa\u8bae\u624b\u52a8\u63a8\u6837\u4f8b\uff0c\uff0c\u4f1a\u5f88\u5bb9\u6613\u7406\u89e3<\/p>\n
<\/p>\n<\/p>\n
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn = + 7; int n, m, cnt; int g[maxn], num[maxn], vis[maxn]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } void init() { memset(vis, 0, sizeof vis); memset(num, 0, sizeof num); scanf(\"%d %d\", &n, &m); cnt = 0; for(int i = 1; i*i <= m; ++i) { if(m % i == 0) { g[cnt++] = i; if(i*i != m) g[cnt++] = m\/i; } } sort(g, g+cnt); for(int i = 0; i < n; ++i) { int x; scanf(\"%d\", &x); int t = gcd(x, m); for(int j = 0; j < cnt; ++j) { if(g[j] % t == 0) { vis[j] = 1; } } } vis[cnt-1] = 0; } void solve() { ll ans = 0; for(int i = 0; i < cnt-1; ++i) { if(vis[i] != num[i]) { int t = (m-1)\/g[i]; ans += (ll)t*(t+1)\/2 * g[i] * (vis[i]-num[i]); t = vis[i] - num[i]; \/\/cout << g[i] << \" = \" << t << endl; for(int j = i; j < cnt; ++j) { if(g[j] % g[i] == 0) num[j] += t; } } } cout << ans << endl; } int main() { int T; scanf(\"%d\", &T); for(int tt = 1; tt <= T; ++tt) { init(); printf(\"Case #%d: \", tt); solve(); } return 0; } <\/code><\/pre><\/p>\n","protected":false},"excerpt":{"rendered":"\u5bb9\u65a5\u5206\u6790_\u5bb9\u65a5\u539f\u7406\u7684\u4e09\u4e2a\u516c\u5f0f\u5bb9\u65a5\u539f\u7406\u9898\u610f\u5f88\u7b80\u5355\uff0c\u5bb9\u6613\u63a8\u51fa\uff0c\u8981\u6c42\uff1a\u5c0f\u4e8em\u7684\u6570\u4e2d\uff0c\u80fd\u591f\u88ab\u6bcf\u4e2a\u9752\u86d9\u6b65\u8ddd\u4e0em\u7684gcd\u6574\u9664\u7684\u6570\u7684\u548c\uff0c...","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\/6747"}],"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=6747"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/6747\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=6747"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=6747"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=6747"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}