1059 Prime Factors (25 分)

題意 ：

• 給一正整數(shù)，要求分解質(zhì)因數(shù)

思路 ：

• 使用is_first，來完成除了第一個(gè)質(zhì)因數(shù)前都有*的效果
• 如果n=1，要特判
• 最后如果n>1，說明還沒有除盡，還有最后一個(gè)質(zhì)因數(shù)

#include <iostream> using namespace std;int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n; cin >> n;cout << n << "=";if (n == 1) cout << n;bool is_first = true;for (int i = 2; i <= n / i; i ++ ){if (n % i == 0){int k = 0;while (n % i == 0) k ++ , n /= i;if (is_first) is_first = false;else cout << '*';cout << i;if (k > 1) cout << "^" << k;}}if (n > 1){if (!is_first) cout << '*';cout << n;} }

1081 Rational Sum (20 分)

• 題意 ：rationnal numbers有理數(shù)；numerator/denominator分子/分母；integer part整數(shù)部分；fractional part小數(shù)部分
• 題意 ：給n個(gè)分?jǐn)?shù)，求和，要寫成真分?jǐn)?shù)且約分
• 思路 ：初始化a為0，b為1；輸出時(shí) ：如果分母是1，直接輸出整數(shù)部分就可以；如果a>b，說明有整數(shù)部分和小數(shù)部分；pat上分子和分母數(shù)據(jù)范圍是long int，相當(dāng)于是int，而acwing是long long，如果沒有中間那步會(huì)溢出，因此分母要變成b和d的最小公倍數(shù)，找到b和d的最大公約數(shù)，那么分母就是b/最大公約數(shù)再*d（原先應(yīng)該是b *d），分子是…（原先是a * d + b * c），但是分子式子的前半部分是由d/t而不是a/t
• 語法 ：gcd模版；scanf時(shí)如果是負(fù)數(shù)這個(gè)符號(hào)是在分子上讀入的

#include <iostream>using namespace std;typedef long long LL;LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a; }int main() {int n;cin >> n;LL a = 0, b = 1;for (int i = 0; i < n; i ++ ){LL c, d;scanf("%lld/%lld", &c, &d);LL t = gcd(c, d);c /= t, d /= t;t = gcd(b, d);a = d / t * a + b / t * c;b = b / t * d;t = gcd(a, b);a /= t, b /= t;}if (b == 1) cout << a;else{if (a > b) printf("%lld ", a / b), a %= b;printf("%lld/%lld", a, b);}return 0; }

1088 Rational Arithmetic (20 分)

• 題意 ：給兩個(gè)分?jǐn)?shù)，分別輸出加減乘除式子，注意分?jǐn)?shù)要轉(zhuǎn)成真分?jǐn)?shù)，給的可能是假分?jǐn)?shù)
• 思路 ：打印時(shí)，先約分，然后判斷分母是否為負(fù)，然后判斷分子是否為負(fù)決定是否需要輸出兩個(gè)半括號(hào)，然后如果分母是1一種情況，否則要看是否是假分?jǐn)?shù)，假分?jǐn)?shù)時(shí)注意是abs，因?yàn)檫@道題會(huì)出現(xiàn)分子為負(fù)也可能出現(xiàn)分母為負(fù)的情況

#include <iostream>using namespace std;typedef long long LL;LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a; }void print(LL a, LL b) {LL t = gcd(a, b);a /= t, b /= t;if (b < 0) a *= -1, b *= -1;bool is_minus = a < 0;if (is_minus) cout << "(";if (b == 1) cout << a;else{if (abs(a) > b) printf("%lld ", a / b), a = abs(a) % b;printf("%lld/%lld", a , b);}if (is_minus) cout << ")"; }void add(LL a, LL b, LL c, LL d) {print(a, b), cout << " + ", print(c, d), cout << " = ";a = a * d + b * c;b = b * d;print(a, b), cout << endl; }void sub(LL a, LL b, LL c, LL d) {print(a, b), cout << " - ", print(c, d), cout << " = ";a = a * d - b * c;b = b * d;print(a, b), cout << endl; }void mul(LL a, LL b, LL c, LL d) {print(a, b), cout << " * ", print(c, d), cout << " = ";a = a * c;b = b * d;print(a, b), cout << endl; }void div(LL a, LL b, LL c, LL d) {print(a, b), cout << " / ", print(c, d), cout << " = ";if (!c) puts("Inf");else{a = a * d;b = b * c;print(a, b), cout << endl;} }int main() {LL a, b, c, d;scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);add(a, b, c, d);sub(a, b, c, d);mul(a, b, c, d);div(a, b, c, d);return 0; }

1096 Consecutive Factors (20 分)

• 題意 ：給一數(shù)，求最長連續(xù)因子
• 思路 ：先枚舉起始位置，然后枚舉長度；注意有可能只有它本身的情況
• 語法 ：$2^{31}$還是int范圍；一直循環(huán)到連續(xù)斷了，就直接退出for循環(huán)

#include <iostream> #include <vector>using namespace std;int main() {int n;cin >> n;vector<int> res;for (int i = 2; i * i <= n; i ++ )if (n % i == 0){vector<int> seq;for (int m = n, j = i; m % j == 0; j ++ ){seq.push_back(j);m /= j;}if (seq.size() > res.size()) res = seq;}if (res.empty()) res.push_back(n);cout << res.size() << endl;cout << res[0];for (int i = 1; i < res.size(); i ++ ) cout << "*" << res[i];return 0; }

1103 Integer Factorization (30 分)

題意 ：

• 正整數(shù) N 的 K?P 分解，是將 N 寫為 K 個(gè)正整數(shù)的 P 次冪的和。
• 請(qǐng)你編寫一個(gè)程序，給定 N,K,P 的情況下，找到 N 的 K?P 分解。
• 注意，答案也許不唯一。
• 你需要輸出各因子之和最大的一種解法。
• 如果仍不能確定唯一解法，則選擇因子序列更大的解法。

思路 ：

1104 Sum of Number Segments (20 分)

• 語法 ：i和n-i+1都是$10^5$，相乘有$10^{10}$，會(huì)超過int，所以那個(gè)公式寫的時(shí)候盡可能把double寫到前面，如果寫到后面會(huì)溢出；（精度？）long double輸出時(shí)是%Lf

#include <iostream>using namespace std;int main() {int n;cin >> n;long double res = 0;for (int i = 1; i <= n; i ++ ){long double x;cin >> x;res += x * i * (n - i + 1);}printf("%.2Lf", res);return 0; } #include <iostream>using namespace std;typedef long long ll;int main() {int n;cin >> n;ll res = 0;for (int i = 1; i <= n; i ++ ){double x;cin >> x;res += (ll)(1000 * x) * i * (n - i + 1); // 乘1000放大數(shù)字，避免精度的影響，注意括號(hào)}printf("%.2lf", res / 1000.0); // 加上.0可以轉(zhuǎn)化成小數(shù)return 0; }

1112 Stucked Keyboard (20 分)

• 題意 ：給k和一字符串，字符串中連續(xù)出現(xiàn)k次的為壞
• 思路 ：用原字符串判斷某個(gè)鍵（數(shù)量固定）是否壞；遍歷原字符串，每種字符只有三種情況，沒壞，壞了但沒被輸出過，壞了但被輸出過，所以不用bool，而用int

#include <iostream>using namespace std;const int N = 200;int st[N]; // 1沒壞，0壞了，2輸出過int main() {string s;int k;cin >> k >> s;for (int i = 0; i < s.size(); i ++ ){int j = i + 1;while (j < s.size() && s[j] == s[i]) j ++ ;int len = j - 1 - i + 1;if (len % k) st[s[i]] = 1;i = j - 1; // 因?yàn)檫€要 ++}string res;for (int i = 0; i < s.size(); i ++ ){if (!st[s[i]]) cout << s[i], st[s[i]] = 2;if (st[s[i]] == 1) res += s[i];else{res += s[i];i += k - 1;}}cout << endl << res << endl;return 0; }

1116 Come on! Let’s C (20 分)

• 題意 ：按排名給id（1e4以內(nèi)的正整數(shù)），根據(jù)詢問的id判斷是否在排名中出現(xiàn)過和是否被詢問過，然后是排名第一和排名是否質(zhì)數(shù)
• 思路 ：先把10^4以內(nèi)的質(zhì)數(shù)先標(biāo)記一下，用篩法求質(zhì)數(shù)，O(nloglogn)；先用過Rank[id]再標(biāo)記為-1；Rank數(shù)組有三種狀態(tài)，Rank==0代表沒有出現(xiàn)過，Rank是-1代表輸出過了，Rank是正整數(shù)代表正常排名且未輸出；st數(shù)組有三種狀態(tài)，0表示篩法時(shí)沒有被篩過（未被染色）在10 ^4以內(nèi)也就只有1，1表示是質(zhì)數(shù)，2表示非質(zhì)數(shù)
• 語法 ：注意觀察發(fā)現(xiàn)輸出時(shí)必須%04d，像這種固定位數(shù)的編號(hào)題；

#include <iostream>using namespace std;const int N = 1e4 + 10;int Rank[N], st[N];void init() {for (int i = 2; i < N; i ++ )if (!st[i]){st[i] = 1;for (int j = i * 2; j < N; j += i)st[j] = 2;} }int main() {init();int n;cin >> n;for (int i = 1; i <= n; i ++ ){int id;cin >> id;Rank[id] = i;}int k;cin >> k;while (k -- ){int id;cin >> id;printf("%04d: ", id);if (!Rank[id]) puts("Are you kidding?");else if (Rank[id] == -1) puts("Checked");else{int t = st[Rank[id]];if (!t) puts("Mystery Award");else if (t == 1) puts("Minion");else puts("Chocolate");Rank[id] = -1;}}return 0; }

1152 Google Recruitment (20 分)

• 題意 ：在給出的一個(gè)L（<=1000）位的數(shù)中找到第一個(gè)K（<10）位的質(zhì)數(shù)
• 思路 ：判斷一個(gè)數(shù)是否是質(zhì)數(shù)，這個(gè)題k最大是9位，就是$10^9?1$，不可能把這之間所有質(zhì)數(shù)都找出來，可以用試除法判斷，既可以用自然數(shù)來試，也可以用質(zhì)數(shù)來試，到$x^{1/2}$，如果用自然數(shù)來試，最壞情況每次試$(10^9{)}^{1/2}$，差不多3e4，最多1000位，所以3e7，有可能會(huì)超時(shí)，我們優(yōu)化一下，試除法的時(shí)候不用自然數(shù)來試而是用質(zhì)數(shù)來試；費(fèi)馬 ：1到n中質(zhì)數(shù)的個(gè)數(shù)大概是$n/(lnn)$，ln(3e4)肯定大于10，也就是可以比自然數(shù)效率高10倍以上；所以這道題就是先將1到$(10^9{)}^{1/2}$以內(nèi)的質(zhì)數(shù)先篩出來，
• 語法 ：這里是先篩質(zhì)數(shù)而不是判斷質(zhì)數(shù)，所以1這個(gè)特殊情況就不用管了，因?yàn)槲覀冎挥玫絧rimes數(shù)組里的東西，st數(shù)組不在這題里用；循環(huán)條件中的primes[i]

#include <iostream>using namespace std;const int N = 4e4;int primes[N], cnt; bool st[N];void init() {for (int i = 2; i < N; i ++ )if (!st[i]){primes[cnt ++ ] = i;for (int j = i * 2; j < N; j += i)st[j] = true;} }bool check(string s) {int x = stoi(s);for (int i = 0; primes[i] <= x / primes[i]; i ++ )if (x % primes[i] == 0)return false;return true; }int main() {init();int l, k;string s;cin >> l >> k >> s;for (int i = 0; i + k <= l; i ++ ){string ss = s.substr(i, k);if (check(ss)){cout << ss;return 0;}}cout << 404;return 0; }

總結(jié)

以上是生活随笔為你收集整理的PAT甲级题目翻译+答案 AcWing（数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。