P2158 [SDOI2008]儀仗隊題解-有解無憂

旅行傳送門：https://www.luogu.com.cn/problem/P2158

題目描述

作為體育委員，C君負責這次運動會儀仗隊的訓練，儀仗隊是由學生組成的N * N的方陣，為了保證隊伍在行進中整齊劃一，C君會跟在儀仗隊的左后方，根據其視線所及的學生人數來判斷隊伍是否整齊(如下圖)，

現在，C君希望你告訴他隊伍整齊時能看到的學生人數，

輸入格式

共一個數N

輸出格式

共一個數，即C君應看到的學生人數，

輸入輸出樣例

輸入 #1

輸出 #1

解題思路

以左下角C君所在的點為原點，第一行為x軸，第一列為y軸建立平面直角坐標系，不難發現，一條直線上只有第一個點能被看見，而直線的斜率 k = y / x，即點(x , y)能被看見的條件為其與原點的連線的斜率是第一次出現；我們又知道，分數化為最簡形式時有：gcd (x , y) = 1,即x與y互質，那么我們的問題就轉化為了求有幾對互質的x與y，

在數論中，對正整數n，歐拉函式是小于或等于n的正整數中與n互質的數的數目(因此φ(1)=1)，因此，方陣下三角中互質的x與y的對數即為(方陣為n * n的大小，而坐標軸的起點是由0開始計算，所以只累加至n - 1)，由于方陣關于y = x對稱，最后輸出答案2 * + 1即可(y = x 上還有一點)，

歐拉函式

度娘與各大神犇對該函式的證明程序遠遠勝過本蒟蒻，在此就不過多贅述了，

AC代碼

 1 //打表版(3~6s)
 2 #include <bits/stdc++.h>
 3 #define MAXN 40000 + 10
 4 
 5 int phi[MAXN],ans[MAXN];
 6 
 7 void euler()
 8 {
 9     ans[1] = 1;
10     for (int i = 1; i <= MAXN; i++)
11     {
12         int res = i, n = i;
13         for (int j = 2; j * j <= n; j++)
14         {
15             if (!(n % j))
16                 res = res * (j - 1) / j;
17             while (!(n % j))
18                 n /= j;
19         }
20         if (n > 1)
21             res = res * (n - 1) / n;
22         phi[i] = res;
23     }
24     for (int i = 2; i <= MAXN; i++)
25         for (int j = 1; j < i; j++)
26             ans[i] += phi[j];
27 }
28 
29 int main(int argc, char const *argv[])
30 {
31     euler();
32     int n;
33     while (~scanf("%d", &n))
34     {
35         if (n == 1) //方陣大小為1*1時特判，此時佇列中只有自己，輸出0
36         {
37             puts("0");
38             continue;
39         }
40         printf("%d\n", 2 * ans[n] + 1);
41     }
42     return 0;
43 }

View Code

 1 //優化版(55±5ms)
 2 #include <bits/stdc++.h>
 3 #define MAXN 40000 + 10
 4 
 5 int main(int argc, char const *argv[])
 6 {
 7     int n, ans;
 8     while (~scanf("%d", &n))
 9     {
10         ans = 0;
11         if (n == 1)
12         {
13             printf("%d\n", 0);
14             continue;
15         }
16         for (int i = 1; i < n; i++)
17         {
18             int res = i, t = i;
19             for (int j = 2; j * j <= t; j++)
20             {
21                 if (!(t % j))
22                     res = res * (j - 1) / j;
23                 while (!(t % j))
24                     t /= j;
25             }
26             if (t > 1)
27                 res = res * (t - 1) / t;
28             ans += res;
29         }
30         printf("%d\n", 2 * ans + 1);
31     }
32     return 0;
33 }

View Code

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/270552.html

標籤：C++

上一篇：現代c++模板元編程：遍歷tuple

下一篇：c++通訊錄管理系統

P2158 [SDOI2008]儀仗隊 題解