描述

作為體育委員，C君負責這次運動會儀仗隊的訓練。儀仗隊是由學生組成的N * N的方陣，為了保證隊伍在行進中整齊劃一，C君會跟在儀仗隊的左后方，根據其視線所及的學生人數來判斷隊伍是否整齊. 現在，C君希望你告訴他隊伍整齊時能看到的學生人數。

分析

• 分析一下, 如果把C的點當做(0, 0), 那么如果點(x, y)的x, y互質的話, 點(x, y)一定可以被看到.
• 問題轉化為如何求小于n的所有互質的數的個數.
• 歐拉函數
• 但歐拉函數篩法求的是小于x的與x互質的數的個數, 如果(x, y)可以被看到, 那么(y, x)也一定能被看到. 所以結果應*2. 不過(1, 1)不用*2
• 又因為以C作為(0, 0), 還有(0, 1)和(1, 0)兩個點沒有被計算進去

代碼

#include using namespace std; typedef long long int lli; const int maxn = 40000 + 10;lli phi[maxn];void euler_phi(int n) {phi[1] = 1;for(int i = 2; i <= n; i++) if(!phi[i])for(int j = i; j <= n; j += i) {if(!phi[j]) phi[j] = j;phi[j] = phi[j] / i * (i-1);} }int main() {int n;scanf("%d", &n);euler_phi(n);lli ans = 0;for(int i = 2; i < n; i++) ans += phi[i];printf("%lld\n", ans*2 + 3);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-2190-仪仗队-SDOI2008-欧拉函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。