费马小定理:假如p是质数，且gcd(a,p)=1，那么
首先是挡板法（隔板法）,然后用即可，高中数学范围不多叙述。
然后得到答案是
这题读入数据大，就算快速幂也肯定TLE，所以用费马小定理，把数据规模降到int 范围内，时间复杂度降低
因为1e9+7是一个素数，(基本可以假设N-1不是1e9+7的倍数，这一点我没想到，所以没写出来。。。。)
所以可以(1e9+7)^N对(1e9+7-1)取余，以下是代码：
#include<iostream>
#include<string.h>
#define MOD 1000000007
using namespace std;
const int N=1e7+1;
//const int MOD=1e9+7;
char s[N];
int maxx;
int main()
{
while(scanf("%s",s)!=EOF)
{
int l=strlen(s);
long long k=0;
s[l-1]-=1;//计算N-1
for(int i=0;i<l;i++)
{
k=k*10+s[i]-'0';
k=k%(MOD-1);//费马小定理
}
//cout<<k<<endl;
long long t=2;
long long ans=1;
while(k>0)
{
if(k%2==0)
{
}
else
{
ans=ans*t%MOD;
}
k/=2;
t=t*t%MOD;
}
cout<<ans<<endl;
}
}
第二题：HDU - 1395
这个题目暴力求出答案：每此取余数即可
如果是偶数，直接跳出,奇数一定成立（证明听说要用欧拉函数，笔者最近在看数论方面的东西，奇数证明部分留个坑。）
#include<iostream>
#include<math.h>
#define ll unsigned long long
using namespace std;
int main()
{
ll n;
while(cin>>n)
{
ll count=1;
ll t=2;
if(n%2==0||n<=1)
{
printf("2^? mod %d = 1\n",n);
}
else
{
while(true)
{
if(t%n==1)break;
count++;//计数
t=t*2%n;
}
printf("2^%d mod %d = 1\n",count,n);
}
}
}
第三题：HDU - 5750
这题关键是素数筛
在素数筛里面最快的就是O(N)的复杂度
用素数和题目中给的d相乘，可以得到一些n的含有d因子的数，然后选择合适的跳出条件（其实观察题目也可以发现，在许多情况下，非常容易跳出，因为样例中有好几个是0）
（以后不管什么题都用long long）
然后又被cin比scanf()慢坑了，改scanf
上代码（有注释）：
#include<iostream>
#include<string.h>
#define ll long long
using namespace std;
const int N=1e5+5;
bool vis[N];
ll prime[N];
ll pri(int n){
memset(vis,1,sizeof(vis));
ll num=0;
for(ll i=2;i<=n;i++)
{
if(vis[i])prime[++num]=i;
for(int j=1;j<=num&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
return num;
}
int main()
{
int t;
cin>>t;
int cnt=pri(N-1);
while(t--)
{
ll ans=0,n,d;
scanf("%lld%lld",&n,&d);//scanf读入 比cin快 用cin会TLE
for(int i=1;i<=cnt;++i)
{
if(prime[i]<=d&&prime[i]*d<n)ans++;//在范围内
if(prime[i]>d||prime[i]*d>=n)break;//超过范围
if(d!=prime[i]&&d%prime[i]==0)break;//枚举了d的因数跳出
}
cout<<ans<<endl;
}
}
