codeforces 111B/112D Petya and Divisors

题目：Petya and Divisors
传送门：

http://codeforces.com/problemset/problem/111/B

http://codeforces.com/problemset/problem/112/D

分析：

　　很容易想到读入x[i]、y[i]，寻找x[i]的因数，判断一下是不是x[i-y[i]]、x[i-y[i]+1]...x[i-1]的某个数因数；但这样会超时；考虑以下两个优化：（1）寻找x[i]因数时循环范围只需要从j∈[0,sqrt(x[i])],但循环体内同时判断两个因数j、x[i]/j(注意当j*j==x[i]的情况);（2）把子问题“判断一下因数j是不是x[i-y[i]]、x[i-y[i]+1]...x[i-1]的某个因数”转变为问题“因数j最后一次位置出现在不在[i-y[i],i-1]”求解，并更新因数j最后一次位置。

代码：

#include<cstdio>
int n,last[100010];
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1,x,y,ans;i<=n;++i){
        scanf("%d%d",&x,&y);
        ans=0;
        for(int j=1;j*j<=x;++j)
            if(x%j==0){
                if(last[j]<i-y)++ans;last[j]=i;
                if(j*j==x)continue;
                if(last[x/j]<i-y)++ans;last[x/j]=i;
            }
        printf("%d
",ans);
    }
    return 0;
}