@KirinBill
2017-09-18T12:17:39.000000Z
字数 3206
阅读 1190
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
x=0;
int pm=1; char c;
do{c=getchar();}while(!isdigit(c) && c!='-');
c=='-' ? pm=-1:x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <queue>
#include <algorithm>
using std::queue;
using std::min;
const int MAXN=100005,P=1e9+7;
inline int cal_ans(int n,int m){
static int fib[MAXN];
static queue<int> die;
while(die.size()) die.pop();
fib[0]=fib[1]=1;
die.push(fib[0]);
for(int i=2,lim=min(n,m);i<=lim;++i){
fib[i]=(fib[i-1]+fib[i-2])%P;
die.push(fib[i-2]);
}
for(int i=m+1;i<=n;++i){
fib[i]=((fib[i-1]+fib[i-2])%P-die.front()+P)%P;
die.pop();
die.push(fib[i-2]);
}
return fib[n];
}
int main(){
setIO("rabbit");
int T;
read(T);
int n,m;
while(T--){
read(n),read(m);
write(cal_ans(n,m),'\n');
}
return 0;
}
upd()
后就不存在了);upd()
时注意分清楚情况,不重不漏地统计就好了;考虑最朴素的暴力写法,设表示当时的答
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j)
ans[i]+=(gcd(i-j,i+j)==1);
}
#include <cstdio>
const int MAXN=1e7+5;
int phi[MAXN];
long long ans[MAXN];
inline void Euler_phi(){
static int prm[MAXN];
static bool notP[MAXN];
notP[1]=true,phi[1]=1;
for(int i=2;i<MAXN;++i){
if(!notP[i]){
prm[++prm[0]]=i;
phi[i]=i-1;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
phi[tmp]=prm[j]*phi[i];
break;
}
else phi[tmp]=phi[i]*phi[prm[j]];
}
}
}
inline void pre_tab(){
Euler_phi();
for(int i=1;i<MAXN;++i){
ans[i]=ans[i-1];
ans[i]+= i&1 ? phi[i]>>1:phi[i];
}
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
pre_tab();
int T;
scanf("%d",&T);
int n;
while(T--){
scanf("%d",&n);
printf("%lld\n",ans[n]);
}
return 0;
}