TCO11 Qual2 Hard(1000) FoxIntegerLevelThree

http://www.topcoder.com/stat?c=problem_statement&pm=11372:FoxIntegerLevelThree

d(n) = (n-1)%9+1

であるから、

xはrepresentable　⇔　x/kがkの倍数となるようなk(1≦k≦9)が存在する。

gcd(1*1,2*2,……,9*9) = 6350400なので、xがrepresentableかどうかは6350400の周期で繰り返す。

#include <vector>
using namespace std;

class FoxIntegerLevelThree{public:
long long count( long long min, long long max )
{
    int N = 6350400;
    vector<bool> f(N+1);
    int c = 0;
    for ( int i=1; i<=N; i++ )
    {
        int t = ((i-1)%9+1)*i;
        if ( t<=N )
            f[t] = true;
        if ( f[i] )
            c++;
    }
    f[0] = f[N];

    long long ans = ((max-min)/N)*c;

    for ( long long i=min+((max-min)/N)*N; i<=max; i++ )
        if ( f[i%N] )
            ans++;
    
    return ans;
}};