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

因为查询是与“时间”有关,那不妨用一个数组标记离当前时间最近的因子,这样对每个查询只需要即可。

/*278ms,396KB*/

int closeset[100001];

int main()
{
    int n, i, j, cnt, x, y, sqrtx;
    SI(n);
    Forr(i, 1, n + 1)
    {
        SII(x, y);
        cnt = 0, sqrtx = sqrt((double)x);
        Forr(j, 1, sqrtx + 1)
            if (x % j == 0)
            {
                if (closeset[j] < i - y) ++cnt;
                if (closeset[x / j] < i - y && j * j != x) ++cnt;
                closeset[j] = closeset[x / j] = i;
            }
        PI(cnt);
    }
    return 0;
}

Comments

comments powered by Disqus