Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 513 Accepted Submission(s): 104
/* ID: LinKArftc PROG: 2441.cpp LANG: C++ */ #include <map> #include <set> #include <cmath> #include <stack> #include <queue> #include <vector> #include <cstdio> #include <string> #include <utility> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define eps 1e-8 #define randin srand((unsigned int)time(NULL)) #define input freopen("input.txt","r",stdin) #define debug(s) cout << "s = " << s << endl; #define outstars cout << "*************" << endl; const double PI = acos(-1.0); const double e = exp(1.0); const int inf = 0x3f3f3f3f; const int INF = 0x7fffffff; typedef long long ll; #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; }
HDU2441 ACM(Array Complicated Manipulation)
原文:http://www.cnblogs.com/LinKArftc/p/4902658.html