8579: 裴蜀定理题意概述给定 n 个整数 (A1,A2,……,An)不全为 0。 设S X1A1X2A2……XnAn) Xi 可取任意整数。求满足(S0)的最小 S。裴蜀定理说两点存在性一定存在一对整数 x,y可以是负数使得方程成立axbyd最小性所有形如 axby 的整数结果全部都是 d 的倍数。因此最小的正整数结果 恰好就是 d 本身。由 裴蜀定理整数序列 A1,A2,…,AnA 1,A 2 ,…,A n的所有整数线性组合恰好能表示成它们最大公约数的倍数因此 最小的正 S 就是gcdA数组所以所有值取绝对然后求最大公约数参考代码#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-合成数题意概述H 数除以 4 余 1 的数1,5,9,13…H‑素数H 数里在 H 数的范围内除 1 和自己外没有别的 H 数因子1 不算 H‑素数不一定是真实素数。H‑合成数一个 H 数能拆成两个 H‑素数相乘可以相同哪怕有别的分解方式也算数不能拆成两个就不算。多组输入给 h读到 0 结束。求 0h 中有多少个 H‑合成数按格式输出 h 和答案。筛出 H‑素数所有 H 数形如 4n1。用类似埃氏筛步长取 4 遍历。若当前数 i 未被标记为合数则 i 是 H‑素数将其与所有 H 数 j 相乘标记乘积为 H‑合数。记录最小 H‑素因子 minP[i]再次遍历所有 H‑素数 p枚举 H 数 q令 minP[p*q] p第一次赋值即为最小因子。计算 H‑素因子个数 cnt[i]设 cnt[i] 表示将 i 分解成 H‑素数的总个数含重数。若 i 是 H‑素数cnt[i] 1否则cnt[i] cnt[i / minP[i]] 1按数值从小到大递推即可。统计答案若 cnt[i] 2说明它恰好由两个 H‑素数相乘即为“H‑合成数”。预处理前缀和数组 pref[h]查询时直接 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: 计算星期几题意概述假设今天是星期日那么过a^b天之后是星期几等价于求a^b(mod7)核心思想b最大 (10^5)直接循环乘会超时需用快速幂取模参考代码#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: 发发发题意概述能否找到一个由数字8组成的正整数且能被n整除呢如果存在找到最小的并输出其位数。题意转化变形8*(10^k-1) 0 mod 9n设 (dgcd(8,n))。推导后得条件必须有 gcd(10,m) 1才有解否则无解输出 0。如果 (gcd(10,m)1)根据欧拉定理存在最小的正整数 k10 模 m 的阶满足10^k 1mod m这个 k 就是答案。通过欧拉定理求k:m欧拉函数的最小约数即是我们要求的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两个long long相乘会溢出要用__int128中转 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; }//求欧拉函数 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的全部约数排序 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; }//质因数分解返回pair质因子,次数 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题意概述给定整数N求1x,yN且Gcd(x,y)为素数的 数对(x,y)有多少对。解题思路若 gcd(x,y) pp 为素数则 x p·a y p·b且 gcd(a,b) 11 ≤ a,b ≤ ⌊N/p⌋。对固定 M1 ≤ a,b ≤ M 且互质的有序对数量F(M) 1 2·Σ_{k2}^{M} φ(k) 2·Σ_{k1}^{M} φ(k) - 1解释(1,1) 一对max(a,b) k ≥ 2 时(k, b) 中与 k 互质的有 φ(k) 个每个无序对对应 2 个有序对。所以答案 Σ_{p≤N, p为素数} F(⌊N/p⌋)。用线性筛一次性求出所有素数、所有 φ(i)再做 φ 的前缀和最后对每个素数 O(1) 累加。复杂度O(N)N10⁷ 可过注意答案和前缀和用 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: 等比数列题意概述已知x和n求S1xx2x3...xn由于结果可能很大你只需要求S mod 9973。解题思路求 S(n) 1 x x² … xⁿ mod 9973n 最大 10⁸不能直接循环用分治二分求和复杂度 O(log² n)。分治公式所有运算都在 mod 9973 下n 2k1奇数S(2k1) S(k) × (1 x^(k1))因为 S(k) 1x…x^k乘上 (1x^(k1)) 正好得到 1x…x^(2k1)。n 2k偶数S(2k) S(k-1) × (1 x^k) x^(2k)S(k-1)(1x^k) S(2k-1)再补上最后一项 x^(2k)。x^(k) 用快速幂每次 O(log n) 求出。不用等比数列求和公式 逆元的原因当 x ≡ 1 (mod 9973) 时 x-1 没有逆元会出错分治对任意 x 都安全。多组数据读到 EOFwhile (cin x n)每组不超过 100 个开销很小。参考代码#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; }