2296 儀仗隊 2008年省隊選拔賽山東
時間限制: 1 s
空間限制: 256000 KB
題目等級 : 大師 Master
題解
題目描述 Description
　　作為體育委員，C君負責這次運動會儀仗隊的訓練。儀仗隊是由學生組成的N * N的方陣，為了保證隊伍在行進中整齊劃一，C君會跟在儀仗隊的左后方，根據其視線所及的學生人數來判斷隊伍是否整齊(如下圖)。
　　
　　現在，C君希望你告訴他隊伍整齊時能看到的學生人數。
輸入描述 Input Description
　　共一個數N。
輸出描述 Output Description
　　共一個數，即C君應看到的學生人數。
樣例輸入 Sample Input
4
樣例輸出 Sample Output
9
數據范圍及提示 Data Size & Hint
對于 30% 的數據，1≤N≤1000
對于 100% 的數據，1≤N≤40000
分類標簽 Tags
山東 省隊選拔賽 2008年

/* 找斜率暴力n^3. */ #include<iostream> #include<cstdio> #include<map> #define MAXN 20001 using namespace std; bool g[MAXN][MAXN]; int ans,n; int main() {scanf("%d",&n);if(n==1){printf("0");return 0;}ans=n*n-1-2*n+4-n+2; for(int i=2;i<=n;i++)for(int j=2;j<=n;j++)g[i][j]=true;for(int i=2;i<=n;i++)for(int j=2;j<i;j++){if(g[i][j]){int xx=i-1,yy=j-1,k=i,l=j;while(k<=n&&l<=n){if(g[k+xx][l+yy]) g[k+xx][l+yy]=false,ans-=2;k=k+xx,l=l+yy;}}}printf("%d",ans);return 0; } /* 坐標i,j互質時合法. 然后暴力gcd. n^2logn. */ #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,ans; int gcd(int a,int b) {if(!b) return a;return gcd(b,a%b); } void slove() {for(int i=2;i<=n-1;i++)for(int j=2;j<=n-1;j++){if(gcd(i,j)==1) ans++;} } int main() {scanf("%d",&n);if(n==1){printf("%d",0);return 0;}ans=2*n-1;slove();printf("%d",ans); } /* o(n)歐拉函數. 剛開始暴力篩出素數 不會處理啊啊啊. */ #include<iostream> #include<cstdio> #define MAXN 40001 #define LL long long using namespace std; LL n,ans,p[MAXN]; void euler() {p[1]=1;for(int i=2;i<=n;i++){if(!p[i])for(int j=i;j<=n;j+=i){ if(!p[j]) p[j]=j;p[j]=p[j]/i*(i-1);}ans+=p[i];} } int main() {scanf("%d",&n);ans=1;n--;euler();printf("%lld",ans*2+1);return 0; }

轉載于:https://www.cnblogs.com/nancheng58/p/6070753.html

總結

以上是生活随笔為你收集整理的Codevs 2296 仪仗队 2008年省队选拔赛山东的全部內容，希望文章能夠幫你解決所遇到的問題。

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