Codeforces: B. Little Elephant and Numbers

The problem is from codeforces http://codeforces.com/problemset/problem/221/B

The problem statement is clear. The answer is to count the number of divisors that has at least one common digit with the original number in the decimal representation. The first ‘stuipid’ solution is to check each divisor, as follows.

#!/usr/bin/env python
# https://helloacm.com

n = int(raw_input())
ans = 0

def C(i, n):
    while i > 0:
        if str(i % 10) in n:
            return 1
        i /= 10
    return 0
    
for i in xrange(1, n + 1):
    if n % i == 0:
        ans += C(i, str(n))
        
print ans

The above will give a time-limite exceed on the ninth test because the given n is quite large, and it takes time to process a large number. The above solution can be improved by checking two divisors at a time, and this leads to the complexity , The checking function can also be shortened by using any function. The solution is given below, which passes the tests within the given time scale.

#!/usr/bin/env python
# https://helloacm.com

n = int(raw_input())
x = int(n ** 0.5)
ans = 0

def C(i, n):
    return 1 if any((ch for ch in str(i) if ch in n)) else 0
    
for i in xrange(1, x + 1):
    if n % i == 0:
        ans += C(i, str(n))
        if i * i != n:
            ans += C(n / i, str(n))

print ans

–EOF (The Ultimate Computing & Technology Blog) —