UVa 12425

#include <stdio.h>
#include <math.h>

#define SIZE 1000002LL
#define SQRTSIZE 1001
#define MAXFACTORS 4097
#define PRIMESTOSIZE 78500

long arrPhi[SIZE], primes[PRIMESTOSIZE], numberOfPrimes, numberOfFactors;
char isNotPrime[SIZE];
long long factors[MAXFACTORS + 1], tempFactors[1 + (MAXFACTORS >> 1) ], arr[MAXFACTORS+2];

void initArrays(){
    long i, j;

    for ( i = 0 ; i < SIZE ; i++ ) arrPhi[i] = i;
    for ( i = 2 ; i < SIZE ; i+=2 ) arrPhi[i] >>= 1;

    primes[numberOfPrimes++] = 2;
    for ( i = 3 ; i < SIZE ; i+=2 ){
        if ( isNotPrime[i>>1] == 0 ){
            if ( i < SQRTSIZE )
                for ( j = i * i ; j < SIZE ; j += i<<1 )
                    isNotPrime[j>>1] = 1;

            primes[numberOfPrimes++] = i;
            for ( j = i ; j < SIZE ; j+=i )
                arrPhi[j] -= arrPhi[j]/i;
        }
    }
}

long long phi( long long n ){
    long long m = n;
    long i;

    if ( n < SIZE ) return arrPhi[n];
    for ( i = 0 ; i < numberOfPrimes && n > 1 ; i++ ){
        if( n % primes[i] == 0){
            do{
                 n /= primes[i];
            }while( n % primes[i] == 0);
            m -= m / primes[i];
        }

        if ( n < SIZE && isNotPrime[n>>1] == 0 ) break;
    }

    if ( n > 1 ) m -= m / n;
    return m;
}

long lowerBound(long long *arr, long n, long long num ){
    long low = 0, high = n, mid;

    while ( low + 1 < high ) {
        mid = ( low + high ) >> 1;
        if ( arr[mid] > num ) high = mid;
        else low = mid;
    }

    return low;
}

void factorize(long long n){
    long i, j, k = 0, limit = (int)(sqrt(n) + 0.5);

    /* factorize n */
    for ( i = 1 ; i <= limit ; i++ ){
        if ( n % i == 0 ){
            factors[k] = i, tempFactors[k] = n/i;
            k++;
        }
    }

    j = k - 1;
    if ( factors[k-1] == tempFactors[k-1] ) j--;
    for ( ; j >=0 ; j--, k++ ) factors[k] = tempFactors[j];
    factors[k] = 1LL<<63; /* dummy, used for lowerbound */
    /* TODO (mooo#1#): Need to factorize numbers using prime factors, to
                       reduce time */
    numberOfFactors = k;
}

void precalculateNumbersForQueries(long long n){
    long i, j;

    factorize(n);
    /* find number of values with gcd( value, n ) <= factor[i]
       multiply all "proper" coprimes of n/factors[i] = factors[nums - i - 1]
       with factor[i],
       then the gcd will be equal to factor[i].
    */
    arr[0] = phi(n);
    for ( i = 1, j = numberOfFactors - 2 ; i < numberOfFactors ; i++, j-- ){
        arr[i] = arr[i-1] + phi(factors[j]);
    }

    arr[i] = arr[i-1]; /* dummy, used in case input x > n */
}

int main(){
    long long n, x;
    long query, kase, tests;

    initArrays();
    scanf("%ld", &tests);
    for( kase = 1 ; kase <= tests ; kase++ ){
        scanf("%lld", &n);
        precalculateNumbersForQueries(n);
        printf("Case %ld\n", kase);
        scanf("%ld", &query);
        while( query-- ){
            scanf("%lld", &x);
            if ( x < 1 ){
                printf("0\n");
                continue;
            }
            printf("%lld\n", arr[lowerBound(factors, numberOfFactors, x)]);
        }
    }

    return 0;
}
/* test with 200560490130 */