sgu-246 Black & White - c++编程基础

题目大意：

给你一个 2?N?1 个珠子组成的环形项链，珠子只有黑色和白色两种颜色，输入 2?N?1 ，要你求出这串项链中最少要有多少个黑色珠子( MAX )，使得对于所有拥有 MAX 个黑色珠子的项链总可以找到一对黑色珠子使得去掉这两个黑色珠子将项链分成两段并且其中总有一段珠子的个数为N。输出这个 MAX 。

解题思路：

首先我们观察发现， ans<=N ，这是显然的，但是显然是 N 。
我们考虑构造一个方案使得有 K 个黑色珠子并且不满足上面的要求，那么 ans=K+1 。
首先如果第1个放了黑色珠子，那么第 1+(n+1) 个一定得放白色珠子，第 1+(n+1)?2 可以放置黑色珠子，意识流之后脑补一下这样构造好像是最大的，那么我们就这么构造了。

我们假设第i个放黑色，那么我们就可以每次隔 n+1 放置一个反色的珠子，比如黑白黑白……..
然后我们发现从i出发最少进行 L=LCM(N+1,2?N?1）N+1 次就会回到i，那么如果i放置黑色，那么这一次轮回一共可以放置 ?L2? 个黑色珠子，然后一共有 2?N?1L 个轮回，那么 K=2?N?1L??L2? ，所以 ans=K+1=2?N?1L??L2?+1

AC代码：

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; int n; int gcd(int a,int b) {return a%b==0?b:gcd(b,a%b);} int main() { scanf("%d",&n); n=n/2+1; int Gcd=gcd(n+1,2*n-1); int L=(long long)(n+1)*(2*n-1)/Gcd/(n+1); printf("%d",(2*n-1)/L*(L/2)+1); return 0; }