8579: 裴蜀定理題意概述給定 n 個(gè)整數(shù) (A1,A2,……,An)不全為 0。 設(shè)S X1A1X2A2……XnAn) Xi 可取任意整數(shù)。求滿足(S0)的最小 S。裴蜀定理說(shuō)兩點(diǎn)存在性一定存在一對(duì)整數(shù) x,y可以是負(fù)數(shù)使得方程成立axbyd最小性所有形如 axby 的整數(shù)結(jié)果全部都是 d 的倍數(shù)。因此最小的正整數(shù)結(jié)果 恰好就是 d 本身。由 裴蜀定理整數(shù)序列 A1,A2,…,AnA 1,A 2 ,…,A n的所有整數(shù)線性組合恰好能表示成它們最大公約數(shù)的倍數(shù)因此 最小的正 S 就是gcdA數(shù)組所以所有值取絕對(duì)然后求最大公約數(shù)參考代碼#include bits/stdc.h using namespace std; int gcd(int a, int b) { if (a 0) a -a; if (b 0) b -b; while (b) { int t a % b; a b; b t; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; int ans 0; for (int i 0; i n; i) { int x; cin x; ans gcd(ans, x); } cout ans \n; return 0; }7489: H-合成數(shù)題意概述H 數(shù)除以 4 余 1 的數(shù)1,5,9,13…H?素?cái)?shù)H 數(shù)里在 H 數(shù)的范圍內(nèi)除 1 和自己外沒(méi)有別的 H 數(shù)因子1 不算 H?素?cái)?shù)不一定是真實(shí)素?cái)?shù)。H?合成數(shù)一個(gè) H 數(shù)能拆成兩個(gè) H?素?cái)?shù)相乘可以相同哪怕有別的分解方式也算數(shù)不能拆成兩個(gè)就不算。多組輸入給 h讀到 0 結(jié)束。求 0h 中有多少個(gè) H?合成數(shù)按格式輸出 h 和答案。篩出 H?素?cái)?shù)所有 H 數(shù)形如 4n1。用類似埃氏篩步長(zhǎng)取 4 遍歷。若當(dāng)前數(shù) i 未被標(biāo)記為合數(shù)則 i 是 H?素?cái)?shù)將其與所有 H 數(shù) j 相乘標(biāo)記乘積為 H?合數(shù)。記錄最小 H?素因子 minP[i]再次遍歷所有 H?素?cái)?shù) p枚舉 H 數(shù) q令 minP[p*q] p第一次賦值即為最小因子。計(jì)算 H?素因子個(gè)數(shù) cnt[i]設(shè) cnt[i] 表示將 i 分解成 H?素?cái)?shù)的總個(gè)數(shù)含重?cái)?shù)。若 i 是 H?素?cái)?shù)cnt[i] 1否則cnt[i] cnt[i / minP[i]] 1按數(shù)值從小到大遞推即可。統(tǒng)計(jì)答案若 cnt[i] 2說(shuō)明它恰好由兩個(gè) H?素?cái)?shù)相乘即為“H?合成數(shù)”。預(yù)處理前綴和數(shù)組 pref[h]查詢時(shí)直接 O(1) 輸出。參考代碼#include bits/stdc.h using namespace std; int main() { vectorint queries; int h, maxH 0; while (cin h h ! 0) { queries.push_back(h); maxH max(maxH, h); } vectorbool isComp(maxH 1, false); vectorint minPrime(maxH 1, 0); vectorint dp(maxH 1, 0); vectorint pref(maxH 1, 0); for (int i 5; i maxH; i 4) { if (!isComp[i]) { for (int j 5; j maxH / i; j 4) { isComp[i * j] true; } } } for (int i 5; i maxH; i 4) { if (!isComp[i]) { for (int j 5; j maxH / i; j 4) { int prod i * j; if (minPrime[prod] 0) { minPrime[prod] i; } } } } for (int n 5; n maxH; n 4) { if (!isComp[n]) { dp[n] 1; } else { int p minPrime[n]; dp[n] dp[n / p] 1; } } for (int i 1; i maxH; i) { pref[i] pref[i - 1]; if (i 5 (i % 4 1) dp[i] 2) { pref[i]; } } for (int h : queries) { cout h pref[h] \n; } return 0; }8429: 計(jì)算星期幾題意概述假設(shè)今天是星期日那么過(guò)a^b天之后是星期幾等價(jià)于求a^b(mod7)核心思想b最大 (10^5)直接循環(huán)乘會(huì)超時(shí)需用快速冪取模參考代碼#include bits/stdc.h using namespace std; const int N 1e410; typedef long long ll; // vector(容量初始值) vectorboolisprim(N1, true); vectorintprim; int fac[N]; ll qpow(int a,int x) { ll res 1; while(x) { if(x 1)res (res * a)%7; x 1; a (a * a)%7; } return res; }//快速冪模版 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; int a,b; cinab; string s[7]{Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday}; couts[qpow(a,b)]; return 0; }8015: 發(fā)發(fā)發(fā)題意概述能否找到一個(gè)由數(shù)字8組成的正整數(shù)且能被n整除呢如果存在找到最小的并輸出其位數(shù)。題意轉(zhuǎn)化變形8*(10^k-1) 0 mod 9n設(shè) (dgcd(8,n))。推導(dǎo)后得條件必須有 gcd(10,m) 1才有解否則無(wú)解輸出 0。如果 (gcd(10,m)1)根據(jù)歐拉定理存在最小的正整數(shù) k10 模 m 的階滿足10^k 1mod m這個(gè) k 就是答案。通過(guò)歐拉定理求k:m歐拉函數(shù)的最小約數(shù)即是我們要求的k參考代碼#include bits/stdc.h using namespace std; typedef long long ll; vectorintprim; vectorpairll,int factor(ll x); ll gcd(ll a,ll b) { return b? gcd(b,a%b):a; } ll qpow(ll a, ll x, ll m) { ll res 1; a % m; while (x) { if (x 1) res (__int128)res * a % m;// res*a兩個(gè)long long相乘會(huì)溢出要用__int128中轉(zhuǎn) x 1; a (__int128)a * a % m; } return res; } ll get_phi(ll x) { ll ans x; auto p factor(x); for(auto [pr,_] : p) { ans ans / pr*(pr-1); } return ans; }//求歐拉函數(shù) phi(x) vectorllget_div(ll num) { auto ft factor(num); vectorlldivs; divs.push_back(1); for(auto [p,cnt]:ft) { int sz divs.size(); ll pe 1; for(int i 1; i cnt ; i) { pe * p; for(int j 0 ; j sz ;j) divs.push_back(divs[j]*pe); } } sort(divs.begin(),divs.end()); return divs; }//獲取num的全部約數(shù)排序 vectorpairll,int factor(ll x) { vectorpairll,intres; for(ll i 2; i * i x ;i) { int cnt 0 ; while(x % i 0) { x / i; cnt; } if(cnt ! 0)res.push_back({i,cnt}); } if(x 1) res.push_back({x,1}); return res; }//質(zhì)因數(shù)分解返回pair質(zhì)因子,次數(shù) int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ll n; int num 1; while(cinn) { if(n 0)break; ll m 9LL*n/gcd(8LL,n); ll ans 0; if(gcd(10LL,m) ! 1)ans 0; else{ ll phi get_phi(m); vectorlldivs get_div(phi); for(ll k : divs) { if(qpow(10,k,m) 1) { ans k; break; } } } coutCase num: ans\n; num; } return 0; }8043: GCD題意概述給定整數(shù)N求1x,yN且Gcd(x,y)為素?cái)?shù)的 數(shù)對(duì)(x,y)有多少對(duì)。解題思路若 gcd(x,y) pp 為素?cái)?shù)則 x p·a y p·b且 gcd(a,b) 11 ≤ a,b ≤ ?N/p?。對(duì)固定 M1 ≤ a,b ≤ M 且互質(zhì)的有序?qū)?shù)量F(M) 1 2·Σ_{k2}^{M} φ(k) 2·Σ_{k1}^{M} φ(k) - 1解釋(1,1) 一對(duì)max(a,b) k ≥ 2 時(shí)(k, b) 中與 k 互質(zhì)的有 φ(k) 個(gè)每個(gè)無(wú)序?qū)?duì)應(yīng) 2 個(gè)有序?qū)?。所以答? Σ_{p≤N, p為素?cái)?shù)} F(?N/p?)。用線性篩一次性求出所有素?cái)?shù)、所有 φ(i)再做 φ 的前綴和最后對(duì)每個(gè)素?cái)?shù) O(1) 累加。復(fù)雜度O(N)N10? 可過(guò)注意答案和前綴和用 long long。參考代碼#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll phi(n 1, 0); vectorbool isComp(n 1, false); vectorint primes; phi[1] 1; for (int i 2; i n; i) { if (!isComp[i]) { primes.push_back(i); phi[i] i - 1; } for (int p : primes) { long long v 1LL * i * p; if (v n) break; isComp[v] true; if (i % p 0) { phi[v] phi[i] * p; break; } else { phi[v] phi[i] * (p - 1); } } } for (int i 2; i n; i) phi[i] phi[i - 1]; ll ans 0; for (int p : primes) { int m n / p; ans 2 * phi[m] - 1; } cout ans \n; return 0; }6283: 等比數(shù)列題意概述已知x和n求S1xx2x3...xn由于結(jié)果可能很大你只需要求S mod 9973。解題思路求 S(n) 1 x x2 … x? mod 9973n 最大 10?不能直接循環(huán)用分治二分求和復(fù)雜度 O(log2 n)。分治公式所有運(yùn)算都在 mod 9973 下n 2k1奇數(shù)S(2k1) S(k) × (1 x^(k1))因?yàn)?S(k) 1x…x^k乘上 (1x^(k1)) 正好得到 1x…x^(2k1)。n 2k偶數(shù)S(2k) S(k-1) × (1 x^k) x^(2k)S(k-1)(1x^k) S(2k-1)再補(bǔ)上最后一項(xiàng) x^(2k)。x^(k) 用快速冪每次 O(log n) 求出。不用等比數(shù)列求和公式 逆元的原因當(dāng) x ≡ 1 (mod 9973) 時(shí) x-1 沒(méi)有逆元會(huì)出錯(cuò)分治對(duì)任意 x 都安全。多組數(shù)據(jù)讀到 EOFwhile (cin x n)每組不超過(guò) 100 個(gè)開(kāi)銷很小。參考代碼#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 9973; ll powmod(ll a, ll k) { a % MOD; ll res 1; while (k) { if (k 1) res res * a % MOD; a a * a % MOD; k 1; } return res; } ll geom(ll x, ll n) { if (n 0) return 1; if (n 1) { ll k n / 2; ll half geom(x, k); return half * (1 powmod(x, k 1)) % MOD; } else { ll k n / 2; ll half geom(x, k - 1); ll res half * (1 powmod(x, k)) % MOD; res (res powmod(x, 2 * k)) % MOD; return res; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll x, n; while (cin x n) { cout geom(x % MOD, n) \n; } return 0; }