# ACM Common algorithm template

2023-01-04   ES

## Article Catalog Common template/algorithm summary @[toc] Lucas seek to combine the number ## Fast -level multiplication model Euler function (Euler screen)

``````

/*
(C n,m) % p
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
ll n, m, p;

ll pow_m(ll a, ll k, ll p) {

ll ans = 1;
ll tmp = a % p;
while (k) {

if (k & 1)ans = ans * tmp % p;
tmp = tmp * tmp % p;
k >>= 1;
}
return ans;
}

ll C(ll n, ll m, ll p) {

if (m > n)return 0;
ll a = 1, b = 1;
for (int i = 1; i <= m; i++) {

a = a * (n + i - m) % p;
b = b * i % p;
}
return a * pow_m(b, p - 2, p) % p;
}

ll Lucas(ll n, ll m, ll p) {

ll ans = 1;
while (n && m) {

ans = ans * C(n % p, m % p, p) % p;
n /= p;
m /= p;
}
return ans;
}

int main() {

int T;
scanf("%d", &T);
while (T--) {

scanf("%lld%lld%lld", &n, &m, &p);
printf("%lld\n", Lucas(n, m, p));
}
return 0;
}

``````

``````/*
Euler screen
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {

int n, cnt = 0;
int prime[100001];// Story of Vegetarian
bool vis[100001]; // Guaranteed not to make a number of prime numbers
scanf("%d", &n);
memset(vis, false, sizeof(vis));// initialization
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++) {

if (!vis[i])// Not the number of prime numbers currently found
prime[cnt++] = i;// Find prime numbers
for (int j = 0; j < cnt && i * prime[j] <= n; j++) {

vis[i * prime[j]] = true;// The number of prime numbers found does not access
if (i % prime[j] == 0) break;// Key! Intersection Intersection Intersection
}

}
printf("%d\n", cnt);
return 0;
}
``````

``````/*
Quick -order multiplication
*/
#include <bits/stdc++.h>
#define _xx ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
typedef long long LL;
//n![1~10]：1,2,6,24,120,720,5040,40320,362880,3628800,
const int mod = 1000000007;
int prime[2000];
bool vis[10005];
int cnt = 0;

void init() {

int m = (int) sqrt(10005) + 1;
for (int i = 2; i <= m; i++) {

if (!vis[i]) {

for (int j = i * 2; j <= 10005; j += i) {

vis[j] = true;
}
}
}
for (int i = 2; i <= 10000; i++) if (!vis[i])prime[cnt++] = i;
}

LL poww(LL a, LL b, LL m) {

LL ans = 1;
while (b) {

if (b & 1) ans = ans * a % m;
a = a * a % m;
b >>= 1;
}
return ans;
}

int main() {

_xx;
init();
int n;
while (cin >> n) {

LL ans = 1;
for (int i = 0; i < cnt && prime[i] <= n; i++) {

int k = 0;
int t = n;
while (t) {

k += t / prime[i];
t /= prime[i];
}
ans = ans * poww(prime[i], k, mod) % mod;
}
cout << ans << endl;
}
}
``````

``````/*
Euler function (Euler screen)
*/
const int N = 10000010;
int phi[N], prime[N];
int tot; // A total of prime numbers
/*
1. pHI (p) = P-1 is only p and p and p with only p and p, which is only p and p, because the factor P and p are only P and P.
2. If I mod p = 0, then pHI (i * p) = pHI (i) * p
3. If I MOD P 3 0, then pHI (i * p) = pHI (i) * (p-)
*/
void Euler() {

memset(phi, 0, sizeof(phi));
phi[1] = 1;
for (int i = 2; i < N; i++) {

if (!phi[i]) {

phi[i] = i - 1;
prime[tot++] = i;
}
for (int j = 0; j < tot && 1ll * i * prime[j] < N; j++) {

if (i % prime[j])
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {

phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}

``````

source