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<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> 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;i<maxn;i++) if(!mark[i]) { prime[res++]=i; for(int j=2*i;j<maxn;j+=i)mark[j]=1; } } 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<res&&prime[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\n",ans*mod_pow(n,mod-2)%mod); } return 0; }