class="markdown_views prism-atom-one-light"> Description 定义Sn=1,2,...,n，问Sn的子集中有多少满足和模n为0的 Input 第一行一整数T表示用例组数，每组用例输入一整数n(T≤300,1≤n≤109) Output 对于每组用例，输出Sn的子集中有多少满足和模n为0的，结果模109+7 Sample Input 5
1
2
3
10
1000 Sample Output 2
2
4
104
618918635 Solution 结论题，ans=1n∑t|n;t是奇数2ntφ(t) 具体细节可以参考我这篇博客：http://blog.csdn.net/V5ZSQ/article/details/77752177 Code #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 44444 #define mod 1000000007 int mark[maxn],prime[maxn],res=0; void get_prime() { for(int i=2;iif(!mark[i]) { prime[res++]=i; for(int j=2*i;j1; } } ll mod_pow(ll a,ll b) { ll ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int phi(int n) { int ans=n; for(int i=0;i*prime[i]<=n;i++) if(n%prime[i]==0) { ans=ans/prime[i]*(prime[i]-1); while(n%prime[i]==0)n/=prime[i]; } if(n>1)ans=ans/n*(n-1); return ans; } ll deal(int d,int n) { return mod_pow(2,n/d)*phi(d)%mod; } int main() { get_prime(); int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); ll ans=0; for(int i=1;i*i<=n;i++) if(n%i==0) { if(i%2)ans=(ans+deal(i,n))%mod; if(i*i!=n&&(n/i)%2!=0)ans=(ans+deal(n/i,n))%mod; } printf("%lld ",ans*mod_pow(n,mod-2)%mod); } return 0; }