zoj3008.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
using namespace std;

int n, m, c;
int ans;
int p[1000], q[1000];

void search(int x, long long k){
    //printf("%d %d %d\n", x, k, n);
    if (k > n) return;
    if (x == c + 1) {
        if (k <= n) ans++;
        return;
    }
    search(x + 1, k);
    int t = 1;
    for (int i = 1; i <= q[x]; i++){
        k *= p[x];
        if (k <= n) search(x + 1, k);
        else break;
    }
}

int main(){
    while (scanf("%d %d", &n, &m) != EOF){
        int i = 2, t = n;
        c = 0;
        while (i * i <= t){
            if (t % i == 0){
                p[++c] = i; q[c] = 0;
                while (t % i == 0) {
                    t /= i; q[c]++;
                }
            }
            i++;
        }
        if (t > 1) { p[++c] = t; q[c] = 1;}
        for (int i = 1; i <= c; i++) q[i] *= m;
        ans = 0;
        search(1, 1);
        printf("%d\n", ans);
    }
    return 0;    
}