首页 > 其他分享 >代码模板

代码模板

时间:2024-01-25 11:45:47浏览次数:40  
标签:phi return int res 代码 exgcd N1 模板

代码模板

数论

快速幂

int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

线性筛法(素数+欧拉函数)

int st[N1], pri[N1], cnt, phi[N1];
int getp(int n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i ++ ) {
		if (!st[i]) pri[ ++ cnt] = i, phi[i] = i - 1;
		for (int j = 1; j <= cnt && pri[j] <= n / i; j ++ ) {
			st[pri[j] * i] = true;
			if (i % pri[j] == 0) {
				phi[pri[j] * i] = phi[i] * pri[j];
				break;
			}
			phi[pri[j] * i] = phi[i] * (pri[j] - 1);
		}
	}
}

扩展欧几里得算法

int exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
    /*
	int d = exgcd(b, a % b, x, y);
	int tmp = x;
	x = y;
	y = tmp - a / b * y;
	*/
    int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

欧拉函数(一个数)

int phi_(int x) {
	int phi = x;
	for (int i = 2; i <= x / i; i ++ ) {
		if (x % i == 0) {
			phi = phi * (i - 1) / i;
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) phi = phi * (x - 1) / x;
	return phi;
}

递推求逆元

void getinv(int n, int p) {
	inv[1] = 1;
	for (int i = 2; i <= n; i ++ ) inv[i] = inv[p % i] * (p - p / i) % p;
}

标签:phi,return,int,res,代码,exgcd,N1,模板
From: https://www.cnblogs.com/MingruiYang/p/17986832

相关文章

  • P3389 【模板】高斯消元法
    #include<bits/stdc++.h>usingnamespacestd;doublemax(doublea,doubleb){ if(a>=b)returna; if(a<b)returnb;}intn;doublea[1010][1010];doublea1[1010][1010];intmain(){ scanf("%d",&n); for(inti=1;i<=n;i++) { ......
  • 10个问题,教你如何使用一个事半功倍的代码托管平台
    源代码是企业最宝贵的资产之一,随着软件规模的不断扩大,企业管理庞大的源代码成为一个重大挑战。为了保持企业员工持续稳定地开展软件开发活动,一个好用的代码管理平台变得尤为重要。代码管理工具是软件开发的基础,能够帮助团队协作更加高效,自动化交付更加流畅。因此,选择一款优秀的代码......
  • 快捷方式,我的代码片段库
    服务端功能接收上传图片,并保存到本地varfiles=Request.Form.Files;varfile=files[0];varfileSavePath="c:\upload\filename.img";using(FileStreamfs=System.IO.File.Create(fileSavePath)){file.CopyTo(fs);//保存原图fs.Flush();}.net类库字符串......
  • P3374 【模板】树状数组 1
    part1#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;structnode1{intl,r,value;};node1node[2000020];inta[500010];voidmt(intp,intl,intr){intmid=(l+r)>>1;node[p].l=l;node[p].r=r;if(l==r)......
  • P3368 【模板】树状数组 2
    #include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintMax=500005;inta[Max];intn,m;intlowbit(intx){ returnx&-x;}voidadd(intx,inty){ while(x<=n){ a[x]+=y; x+=lowbit(x); }}intsum(intx)......
  • 用C++11打造智能观察者模式:详解实现步骤完整示例代码
     观察者模式是一种行为设计模式,其中一个对象(主题)维护其依赖对象(观察者)的列表,当主题的状态发生变化时,它通知所有观察者。以下是一个使用C++11实现观察者模式的简单例子:定义观察者接口(Observer): 创建一个观察者接口,该接口包含观察者需要实现的更新方法。这个接口可以包含其他......
  • Python设计模式:你的代码真的够优雅吗?
    当涉及到代码优化时,Python作为一种高级编程语言,具有广泛的应用领域和强大的功能。在软件开发中,设计模式是一种被广泛采用的解决问题的方案,它提供了一种在特定情境中重复使用的可行方案。在Python中,有许多设计模式可以用来优化代码。其中两种常见的设计模式是单例模式和工厂模式。......
  • R语言量化交易RSI策略:使用支持向量机SVM|附代码数据
    原文链接:http://tecdat.cn/?p=19839机器学习算法可用于找到最佳值来交易您的指标 ( 点击文末“阅读原文”获取完整代码数据)。相对强弱指标(RSI)是最常见的技术指标之一。它用于识别超卖和超买情况。传统上,交易者希望RSI值超过70代表超买市场状况,而低于30则代表超卖市场状况。但是......
  • PYTHON 用几何布朗运动模型和蒙特卡罗MONTE CARLO随机过程模拟股票价格可视化分析耐克
    原文链接:http://tecdat.cn/?p=27099最近我们被客户要求撰写关于蒙特卡罗的研究报告,包括一些图形和统计输出。金融资产/证券已使用多种技术进行建模。该项目的主要目标是使用几何布朗运动模型和蒙特卡罗模拟来模拟股票价格。该模型基于受乘性噪声影响的随机(与确定性相反)变量该项......
  • 代码重构技巧
    1、面向对象类封装性,避免属性直接赋值,而应该使用方法暴露#1改造前publicvoidapprove(finallongbookId){...book.setReviewStatus(ReviewStatus.APPROVED);...}#2改造后publicvoidapprove(finallongbookId){...book.approve();...}2、复数命名:不使用Lis......