题目链接:
题意:由2n-1个珠子组成的项链(肯定是环对吧)。珠子由黑白两色。如果指定两个珠子,那么这两个珠子会把环分成左右两块,不妨设这两块的大小分别为x和y(显然x+y+2=2n-1)。如果存在两个黑珠子使得x和y中至少存在一个为n,则称这个项链是合法的项链。给定N(N=2*n-1),问至少要多少个黑珠子才能使得所有的项链都是合法的?
思路:现在转化一个思路,我们要放尽可能多的黑珠子(设为p)使得任意两个黑珠子之间的珠子都不是n,则答案为p+1。不妨在1位置放了黑珠子,那么2+n位置就必须要放白珠子,1+2(n+1)的位置就可以放黑珠子,这样由黑白两种珠子组成一个交替的环以黑珠子开始以黑珠子结尾,那么我们有k1*(n+1)+1=k2*(2n-1)+1。所以环的个数a=Gcd(2n-1,n+1),每个环的长度L=(2n-1)/a,每个环上有黑珠子L/2个,则p=L/2*a.
i64 n;i64 Gcd(i64 x,i64 y){ return !y?x:Gcd(y,x%y);}int main(){ RD(n); i64 p=Gcd(n,n/2+2); i64 ans=n/p/2*p+1; PR(ans); return 0;}