zoj2666.cpp

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

#include <algorithm>
using namespace std;

int count(int m, int i){
    int ret = 0;
    while (m % i == 0) {
        m /= i;
        ret++;
    }
    return ret;
}

int n, m;
int p[1000], q[1000], cp[1000];

int main(){
    
  while(  scanf("%d %d", &n, &m) != EOF){
    n--;
    int i = 2, c = 0;
    while (i * i <= m){
        if (m % i == 0){
            p[c] = i; q[c] = 0;
            while (m % i == 0){ m /= i; q[c]++; }
            c++;
        }
        i++;
    }
    if (m > 1) { p[c] = m; q[c++] = 1;}
    memset(cp, 0, sizeof(cp));
    int ans = 0, t;
    int a[100000];
    for (int i = 0 ; i < n; i++){
        t = 0;
        for (int j = 0; j < c; j++){
            cp[j] += count(n - i, p[j]) - count(i + 1, p[j]);
            if (cp[j] >= q[j]) t++;
        }
        if (t == c) a[ans++] = i;
    }
    printf("%d\n", ans);
    if (ans)
        for (int i = 0 ; i < ans; i++) printf("%d%c", a[i] + 2, (i == ans - 1) ? '\n' : ' ');
    else puts(""); 
  }
    return 0;   
}