原题链接：http://www.gdfzoj.com/oj/contest/125/problems/3 标签：SG函数，快速幂 Problem 549: Homework of Politics Time Limit: 1000 ms Memory Limit: 262144 KB Problem Description 在政治课之后，老师给学生布置了一个家庭作业。 但是，Maple和TMK都不想做作业。 所以他们决定玩一个游戏，输的人要做他们的作业。 这个游戏就是这样的。 Maple首先从[1，n]中选择一个或多个数字，他可以选择所有数字，但每个数字最多可以被选出一次。 我们认为Maple选择了m个数字，即a1，a2，…，am。 然后他们会找到m堆石头，对于第i堆石头，有ai块石头。 然后，Maple和TMK将轮流玩游戏，Maple先手。 在每一次操作，操作的人应该选择一堆石头，并从这个堆里取一块或多块石头。 而且有一个限制条件，设你选择的这堆石子的取之前的个数为N个，取完后的个数为M个，需要满足N%M==0,M!=0 不能做任何事情的人都会输掉游戏。 现在，Maple想知道他可以从[1，n]中选择多少种方式，能确保他赢得比赛。 Input 一行包含一个整数n 对于30%的数据,1<=n<=100 对于50%的数据,1<=n<=10000 对于100%的数据，1<=n<=1000000 Output 一行包含一个整数对 1000000007 取模 Sample Input 8 Sample Output 192
我们可以发现：
SG(x)=将x质因数分解的指数的和SG函数的值是连续的SG(i)(0<=i<=x) 的值域是 [0,log2x] （想一想，为什么）考虑到 ∑ni=0Cin=2n−1 ，所以就能够得到公式，用一个快速幂就可以解决。 注意一点，当输入1是要特判输出0，不然会wa。
#include<cstdio> #define ha 1000000007 typedef long long ll; ll n,t1,t2; inline ll power(ll a,ll b) { ll ans=1; while (b) { if (b&1) ans=ans*a%ha; b>>=1; a=(a*a)%ha; } return ans; } inline ll log_(ll x) { ll ans=0; while (x^1) {ans++;x>>=1;} return ans; } int main() { scanf("%lld",&n); if (n==1) {printf("0"); return 0;} t1=log_(n); t2=log_(t1); printf("%lld",power(2,n-t2-1)*(power(2,t2+1)-1)%ha); return 0; }