kuangbin带你飞专题十四数论基础

1370 Bi-shoe and Phi-shoe 题意

找出比自己大且欧拉函数也比自己大的第一个数

思路

很巧妙, 找比自己大的第一个质数就可以， 因为质数x, ϕ ( x ) = x − 1 \phi(x) = x-1 ϕ(x)=x−1

代码

#include
#include
using namespace std;
const int maxn = 1e6 + 5;
int prime[maxn];void doprime(){memset(prime,0,sizeof(prime));prime[1]=1;for(int i=2;i*i<maxn;i++){if(!prime[i]){for(int j=2*i;j<maxn;j+=i){prime[j]=1;}}}
}int solve(int n){for(int i=n+1;;i++){if(!prime[i])return i;}
}int main(){int t,n,num,cas=1;doprime();cin>>t;while(t--){long long ans = 0;cin>>n;for(int i=0;i<n;i++){cin>>num;ans += solve(num);}///Case 1:22cout<<"Case "<<cas++<<": "<<ans<<" Xukha"<<endl;}
}

1341 and the 题意

找出所有的约数对数, 并且满足对内的元素不小于b

思路

步骤：

筛质数分解质因数，求约数个数因为求对数ans，有重复，除以ans / 2，dfs筛所有约数减去小于b的情况的约数

注意： 筛所有约数记得排序 代码

#include
#include
#include
#define dbg(a) cout<<#a<<" : "<<a<<endl
using namespace std;typedef long long LL;
typedef pair<LL, int> PII;
const int N = 1000010;int primes[N];
int cnt;
int cntf, cntd;
LL divisor[N];
PII factor[N];
bool st[N];// 筛质数
void init() {for(int i = 2; i < N; i ++){if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}void dfs(LL u, LL p){if(u > cntf) {divisor[cntd ++] = p;return;}for(int i = 0; i <= factor[u].second; i ++) {dfs(u + 1, p);p = (LL) p * factor[u].first;}
}int main(){init();int T;cin >> T;for(int k = 1; k <= T; k ++) {cntd = cntf = 0;LL a, b;cin >> a >> b;if(a< b * b) {printf("Case %d: 0\n", k);continue;}printf("Case %d: ", k);LL sum = 1;// 质因子分解for(int i = 0; primes[i] <= a / primes[i]; i ++) {LL p = primes[i];if(a % p == 0) {LL s = 0;while(a % p == 0) {a /= p;s ++;}factor[++ cntf] = {p, s};sum = (LL)sum * (s + 1);}}if(a > 1) {factor[++ cntf] = {a, 1};sum = (LL)sum *(1 + 1);}sum /= 2;//筛约数dfs(1, 1);sort(divisor, divisor + cntd);for(int i = 0; i < cntd; i ++) {if(b <= divisor[i]) break;sum --;}printf("%lld\n", sum);}return 0;}

- 1282 and 思路

太妙了，简直就是妙蛙种子吃着妙脆角妙进了米奇妙妙屋.

看大佬博客的。

取后三位，快速幂取模就行。LL trail = qmi(n, k, 1000);取前三位就太喵了。

n k = 1 o l g n k = 1 0 k ∗ l g n n^k = 1o^{lgn^k} = 10^{k*lgn} nk==10k∗lgn

设 k ∗ l g n = a + b k*lg^n = a + b k∗lgn=a+b,a是值 k ∗ l g n k*lg^n k∗lgn 的整数部分, b是小数部分， 则 n k = 1 0 a ∗ 1 0 b n^k = 10^a * 10^b nk=10a∗10b。

可以看出 1 0 a 10^a 10a不会改变 n k n^k nk的大小，所以前三位取决于 1 0 b 10^b 10b

所以只需求b出来即可，怎么求呢?

用到个库函数可以求浮点数的小数部分,设为y。modf()

所以前三位为: pow(10, y) * 100;

若不足，输出语句添上补0即可 代码

#include
#include
#include
#includeusing namespace std;typedef long long LL;LL qmi(LL a, LL b, LL p) {LL res = 1;while(b) {if(b & 1) res = (LL)res * a % p;a = (LL) a * a % p;b >>= 1;}return res;
}int main() {int T;cin >> T;for(int i = 1; i <= T; i ++) {LL n, k;cin >> n >> k;LL trail = qmi(n, k, 1000);double x, y;y = modf((double) k * log10(n), &x);LL lead = pow(10, y) * 100;printf("Case %d: lld lld\n",i, lead,trail);}return 0;
}

- 1220 思路

又是质因子分解咯

N = p 1 c 1 ∗ p 2 c 2 ∗ . . . ∗ p k c k N = p_1^{c1} * p_2^{c2} * ...* p_k^{c_k} N=p1c1​∗p2c2​∗...∗pkck​​

要想化成 b a b^a ba ，则 N = ( p 1 c 1 / a ∗ p 2 c 2 / a ∗ . . . ∗ p k c k / a ) a N = (p_1^{c1/a} * p_2^{c2/a} * ...* p_k^{c_k/a})^a N=(p1c1/a​∗p2c2/a​∗...∗pkck​/a​)a

则求 a = g c d ( c 1 , c 2 , c 3 , . . . , c k ) a = gcd(c1, c2, c3, ..., ck) a=gcd(c1,c2,c3,...,ck)即可

注意当是负数的时候要特殊处理, 则幂 a a a 不能是偶数

代码

#include
#include
#includeusing namespace std;const int N = 100010;int primes[N];
bool st[N];
int cnt;void init() {for(int i = 2; i < N; i ++){if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}int gcd(int a, int b){return b?gcd(b, a % b):a;
}
int main() {init();int T;scanf("%d", &T);for(int k = 1; k <= T; k ++) {int n;int f = 0;scanf("%d", &n);if(n < 0) {n = -n, f = 1;}int d = 0;for(int i = 0; i < cnt; i ++) { // primes[i] < n / primes[i]也可if(n % primes[i] == 0) {int s = 0;while(n % primes[i] == 0) {s ++, n /= primes[i];}if(d == 0) d = s;else d = gcd(d, s);}}if(n > 1) d = gcd(d, 1);if(f) {while(d % 2 == 0) d >>= 1;}printf("Case %d: %d\n",k, d);}return 0;}

- 1234 思路

结论题咯。

N较小，暴力求解。

N较大， a n s = l o g ( n ) + C + 1.0 / ( 2 ∗ n ) , ( C = 0. ) 欧 拉 常 数 ans = log(n) + C + 1.0/(2 * n), (C = 0.) 欧拉常数 ans=log(n)+C+1.0/(2∗n),(C=0.)欧拉常数

代码

#include
#include
#include
#includeusing namespace std;const int N = 100010;
const double r = 0.57721566490153286060651209;
double s[N];int main() {for(int i = 1; i < N; i ++) {s[i] = s[i - 1] + 1.0 / i;}int T;scanf("%d", &T);for(int t = 1; t <= T; t ++) {int n;scanf("%d", &n);if(n < N) printf("Case %d: %.10f\n",t, s[n]);else printf("Case %d: %.10f\n", t, log(n) + r + 1.0/(2 * n));}return 0;
}

- 1214 Large 思路

大数除法

代码

#include
#include
#include
#includeusing namespace std;
typedef long long LL;int main(){int T;scanf("%d", &T);for(int k = 1; k <= T; k ++) {vector<int> A;string str;cin >> str;LL b;cin >> b;if(b < 0) b = -b;for(int i = 0; i < str.size(); i ++) {if(str[i] == '-') continue;else A.push_back(str[i] - '0');}LL t = 0;for(int i = 0; i < A.size(); i ++) {t = t * 10 + A[i];t %= b;}if(t == 0) printf("Case %d: divisible\n", k);else printf("Case %d: not divisible\n", k);}return 0;
}

import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner s = new Scanner(System.in);int t = s.nextInt();int cas=1;while(t-->0){BigInteger a = s.nextBigInteger();BigInteger b = s.nextBigInteger();b=b.abs();if(a.mod(b)==BigInteger.ZERO){System.out.println("Case "+cas+": "+"divisible");cas++;}else{System.out.println("Case "+cas+": "+"not divisible");cas++;}}}
}

- Hanzo 思路

二次筛法咯。

线性筛 + 埃氏筛法

代码

#include
#include
#includeusing namespace std;const int N = 1000010;
int primes[N];
int cnt;
bool st[N];typedef long long LL;void init(int n) {memset(st, 0, sizeof st);cnt = 0;for(int i = 2; i < N; i ++) {if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}
int main() {int T;init(50000);scanf("%d", &T);for(int k = 1; k <= T; k ++) {int l, r;scanf("%d%d", &l, &r);memset(st, false, sizeof st);for(int i = 0; i < cnt; i ++) {LL p = primes[i];// 二次筛,筛区间质数, 这里要p*2, 防止结果l等于p，把p也给筛咯for(LL j = max((l + p - 1) / p * p, p * 2); j <= r; j += p)//偏移量, 若太大存不住st[j - l] = true;}cnt = 0;for(int i = 0; i <= r - l; i ++) {// 把1情况去掉if(!st[i] && i + l >= 2)cnt ++;}printf("Case %d: %d\n", k, cnt);}return 0;
}

- 1138 (III) 思路

N！中分解质因子 其中的 5 k 5^k 5k, 质因子5的幂k有多大, 则后面就有多少个0

类似阶乘分解的题。

即 N ! N! N!, 计算其中质因子5的幂。

利用 下面代码计算N!中, p的幂s

for(LL i = n; i; i /= p) {s += i / p;}

然后利用二分来枚举最优解咯

#include
#include
#includeusing namespace std;typedef long long LL;LL num;LL solve(LL n) {LL s = 0;for(LL i = n; i; i /= 5) {s += i / 5;}return s;
}int main() {int T;scanf("%d", &T);for(int t = 1; t <= T; t ++) {scanf("%lld", &num);LL l = 1, r = 1e12;while(l < r) {int mid = l + r >> 1;if(solve(mid) >= num) r = mid;else l = mid + 1;}if(solve(l) == num)printf("Case %d: %lld\n", t, l);else printf("Case %d: impossible\n", t);}return 0;
}

POJ - 2115 C 题意

求最小x满足, a x + b ≡ c ( m o d 2 k ) ax + b \equiv c \ (mod \ 2^k) ax+b≡c(mod2k)

思路

a + c x = b + y ∗ 2 k a + cx = b + y*2^k a+cx=b+y∗2k

c x − 2 k ∗ y = b − a cx - 2^k*y = b - a cx−2k∗y=b−a

c x + 2 k ∗ y ′ = b − a cx + 2^k*y' = b - a cx+2k∗y′=b−a

用扩展欧几里得算法求即可

a x + b y = g c d ( a , b ) ax + by = gcd(a,b) ax+by=gcd(a,b)通解:

{ x = x 0 + b g c d ( a , b ) ∗ t y = y 0 − a g c d ( a , b ) ∗ t \left\{ \begin{} & x = x_0 + \frac{b}{gcd(a, b) } * t \\ & y = y_0 - \frac{a}{gcd(a, b)} * t \end{} \right. ⎩⎪⎪⎨⎪⎪⎧​​x=x0​+gcd(a,b)b​∗ty=y0​−gcd(a,b)a​∗t​

代码

#include
#include
#includeusing namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL &x, LL &y) {if(!b) {x = 1, y = 0;return a;}LL x1, y1;LL d = exgcd(b, a % b, x1, y1);x = y1;y = x1 - a / b * y1;return d;}
int main() {LL a, b, c, k;while(~scanf("%lld%lld%lld%lld", &a, &b, &c, &k) && a + b + c + k) {LL z = (LL)1 << k;LL x, y;LL d = exgcd(c, z, x, y);LL p = b - a;if(p % d != 0) puts("FOREVER");else {x = (LL)x * (p / d);LL t = z / d;x = (x % t + t) % t;printf("%lld\n", x);}}return 0;
}

SGU - 106 The 思路

扩展欧几里得+区间交集+细节处理