找规律

其他

HDU2441

规律：只要这个数的因子中存在平方数，那么这个数就不在数组里
kuangbin的大数模板敲起来也不是很麻烦

#define DLEN 4
#define MAXN 9999
const int maxn = 66000;
int num[maxn];
int prime[maxn];
int cnt;
char str[1000];
void init() {
    cnt = 0;
    memset(num, -1, sizeof(num));
    for (int i = 2; i <= (maxn >> 1); i ++) {
        for (int j = (i << 2); j <= maxn; j += i) num[j] = 0;
    }
    for (int i = 2; i <= maxn; i ++) {
        if (num[i]) prime[cnt ++] = i;
    }
}
class BigNum {
    private:
        int a[1000];
        int len;
    public:
        BigNum() { len = 1; memset(a, 0, sizeof(a)); }
        BigNum(const char*);
        BigNum(const BigNum &);
        BigNum &operator=(const BigNum &);
        BigNum operator+(const BigNum &) const;
        BigNum operator-(const BigNum &) const;
        BigNum operator*(const BigNum &) const;
        BigNum operator/(const int &) const;
        int operator%(const int &) const;
        void print();
};
BigNum::BigNum(const char*s) {
    int t, k, index, L, i;
    memset(a, 0, sizeof(a));
    L = strlen(s);
    len = L / DLEN;
    if (L % DLEN) len ++;
    index = 0;
    for (i = L - 1; i >= 0; i -= DLEN) {
        t = 0;
        k = i - DLEN + 1;
        if (k < 0) k = 0;
        for (int j = k; j <= i; j ++) t = t * 10 + s[j] - '0';
        a[index ++] = t;
    }
}
BigNum::BigNum(const BigNum &T):len(T.len) {
    int i;
    memset(a, 0, sizeof(a));
    for (i = 0; i < len; i ++) a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n) {
    int i;
    len = n.len;
    memset(a, 0, sizeof(a));
    for (i = 0; i < len; i ++) a[i] = n.a[i];
    return *this;
}
BigNum BigNum::operator/(const int &b) const {
    BigNum ret;
    int i, down = 0;
    for (int i = len - 1; i >= 0; i --) {
        ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
        down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
    }
    ret.len = len;
    while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len --;
    return ret;
}
int BigNum::operator%(const int &b) const {
    int i, d = 0;
    for (int i = len - 1; i >= 0; i --) d = ((d * (MAXN + 1)) % b + a[i]) % b;
    return d;
}
void BigNum::print() {
    int i;
    printf("%d", a[len-1]);
    for (int i = len - 2; i >= 0; i --) printf("%04d", a[i]);
    printf("\n");
}
int main() {
    init();
    while (~scanf("%s", str)) {
        if (str[0] == '0') break;
        if (strlen(str) == 1 && str[0] == '1') {
            printf("no\n");
            continue;
        }
        BigNum n = BigNum(str);
        int count;
        for (int i = 0; i < cnt; i ++) {
            count = 0;
            BigNum tmp = n;
            while (tmp % prime[i] == 0) {
                count ++;
                tmp = tmp / prime[i];
                if (count >= 2) break;
            }
            if (count >= 2) break;
        }
        if (count >= 2) printf("no\n");
        else printf("yes\n");
    }
    return 0;
}