codeforces - 85 - D (py)

D.py

#!/usr/bin/env python
"""(c) gorlum0 [at] gmail.com"""
import itertools as it
from sys import stdin
maxn = 10**5

def get_divisors(n, _cache = {}):
    if n not in _cache:
        divisors = []
        for i in xrange(1, int(n**0.5) + 1):
            if not n % i:
                divisors.extend([i, n//i])
        _cache[n] = list(set(divisors))
    return _cache[n]

def solve(n, xss):
    lastdiv = [0] * (maxn+1)
    for i in xrange(1, n+1):
        x, y = next(xss)
        uncommon = 0
        ## print x, get_divisors(x)
        for d in get_divisors(x):
            if not lastdiv[d] >= i-y:
                uncommon += 1
            lastdiv[d] = i
        yield uncommon

def main():
    for line in stdin:
        n = int(line)
        xss = (map(int, next(stdin).split()) for _ in xrange(n))
        print '\n'.join(map(str, solve(n, xss)))

if __name__ == '__main__':
    main()