[poj2368]Buttons_博弈论

Buttons poj-2368

题目大意：给定n个按钮，每次可以按动[1,t]个。求最小的t使得先手必败。

注释：$1\le n\le 10^8$。

想法：经典巴什博弈。

求n的最小非1约数-1即可。

最后，附上丑陋的代码… …

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
int main()
{
int n; cin >> n ;
int minn=n;
for(int i=1;i*i<=n;i++)
{
if(!n%i)
{
if(i>2) minn=min(minn,i);
if(n/i>2) minn=min(minn,n/i);
}
}
if(minn>2) cout << minn-1 << endl ;
else cout << 0 << endl ;
return 0;
}

小结：无。