当前位置:网站首页>Introduction to number theory (greatest common divisor, prime sieve, inverse element)
Introduction to number theory (greatest common divisor, prime sieve, inverse element)
2022-07-06 08:00:00 【D αī s ч】
One 、 greatest common divisor (gcd)
ll gcd(ll x, ll y)
{
return y ? gcd(y, x % y) : x;
}
gcd(a,b,c)=gcd(a,b-a,c-b) Most of them can be promoted
Two 、 Prime sieve ( Euler screen , For Euler function )
int least[maxn], prime[maxn], phi[maxn], tot;
void euler(int n)
{
int i, j;
for (i = 2; i <= n; i++)
{
if (!least[i])
{
least[i] = i;
prime[++tot] = i;
phi[i] = i - 1;
}
for (j = 1; j <= tot && i * prime[j] <= n; j++)
{
least[i * prime[j]] = prime[j];
if (i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
}
3、 ... and 、 Fast power inverse ( Used for finding large combinatorial numbers )
// Calculate large numbers (a/b)mod c
ll quick_pow(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ans;
}
ll inv(ll a, ll b)
{
return (a * quick_pow(b, mod - 2)) % mod;
}
ll fa[maxn], fb[maxn];
ll power(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll C(ll n, ll k)
{
if (k<0 || k>n)
return 0;
return fa[n] * fb[k] % mod * fb[n - k] % mod;
}
void init()
{
int i;
fa[0] = 1;
fb[0] = 1;
for (i = 1; i < maxn; i++)
{
fa[i] = fa[i - 1] * i % mod;
fb[i] = power(fa[i], mod - 2) % mod;
}
}
边栏推荐
- Solution: système de surveillance vidéo intelligent de patrouille sur le chantier
- flask返回文件下载
- The State Economic Information Center "APEC industry +" Western Silicon Valley will invest 2trillion yuan in Chengdu Chongqing economic circle, which will surpass the observation of Shanghai | stable
- Hackathon ifm
- File upload of DVWA range
- onie支持pice硬盘
- Iterator Foundation
- Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
- Circuit breaker: use of hystrix
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
猜你喜欢
数据治理:主数据的3特征、4超越和3二八原则
08- [istio] istio gateway, virtual service and the relationship between them
Machine learning - decision tree
24. Query table data (basic)
NFT smart contract release, blind box, public offering technology practice -- jigsaw puzzle
Nft智能合约发行,盲盒,公开发售技术实战--合约篇
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Opencv learning notes 8 -- answer sheet recognition
esRally国内安装使用避坑指南-全网最新
Solution: intelligent site intelligent inspection scheme video monitoring system
随机推荐
Sanzi chess (C language)
HTTP cache, forced cache, negotiated cache
Circuit breaker: use of hystrix
Chinese Remainder Theorem (Sun Tzu theorem) principle and template code
数据治理:主数据的3特征、4超越和3二八原则
在 uniapp 中使用阿里图标
Understanding of law of large numbers and central limit theorem
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Hackathon ifm
"Designer universe" Guangdong responds to the opinions of the national development and Reform Commission. Primary school students incarnate as small community designers | national economic and Informa
Onie supports pice hard disk
上线APS系统,破除物料采购计划与生产实际脱钩的难题
使用 BR 恢复 S3 兼容存储上的备份数据
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Asia Pacific Financial Media | female pattern ladyvision: forced the hotel to upgrade security. The drunk woman died in the guest room, and the hotel was sentenced not to pay compensation | APEC secur
Webrtc series-h.264 estimated bit rate calculation
Get the path of edge browser
On why we should program for all
[factorial inverse], [linear inverse], [combinatorial counting] Niu Mei's mathematical problems
22. Empty the table