題面

題解

當$(x,y)$能被看到時，$gcd(x,y)=1$，

所以可以求$\sum_{i=0}^n\sum_{j=0}^n[gcd(x,y)=1]$

或者用歐拉函數(shù)

代碼

#include<bits/stdc++.h> #define RG register #define clear(x, y) memset(x, y, sizeof(x)); using namespace std;template<typename T> inline T read() {T data=0, w=1;char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') w=-1, ch=getchar();while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();return data*w; }const int maxn(40010); int phi[maxn], prime[maxn], cnt; bool is_prime[maxn];int getphi(int n) {for(RG int i=2;i<=n;i++){if(!is_prime[i]){prime[++cnt]=i;phi[i]=i-1;}for(RG int j=1;j<=cnt;j++){if(prime[j]*i>n) break;is_prime[prime[j]*i]=true;if(!(i%prime[j])) {phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);}} }int n, ans; int main() {n=read<int>();getphi(n);if(n==1) return printf("0\n")&0;for(RG int i=3;i<=n;i++) ans+=phi[i-1];printf("%d\n", (ans<<1)+3);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cj-xxz/p/10185834.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【SDOI2008】仪仗队的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。