sgu-246 Black & White

sgu-246 Black & White

題目大意：

給你一個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;
}