取余 Cpp的引用

#数学 #cpp

加减乘次方

  1. 加法律：(a+b) %c = ((a %c) + (b %c)) %c。
  2. 减法律：(a-b) %c = ((a %c) - (b %c)) %c。
  3. 乘法律：(ab) %c = ((a %c) (b %c)) %c。
  4. 次方律：a^b % c = ((a % c)^b)% c。

除法

多个数连乘后进行除法取余，为了防止爆long long需要将a/b变为a*b（逆元）%p进行计算，将其称为b在模p上的乘法逆元。逆元存在的充要条件时 b 和 p 互质

法1 快速幂求解逆元

 #include<iostream>  
 #include<algorithm>  
 using namespace std;  
 typedef long long LL;  
 int qmi(LL a, LL b, LL mod){  
     LL res = 1;  
     while(b){  
         if(b & 1) res = res * a % mod;  
         b >>= 1;  
         a = a * a % mod;  
     }  
     return res;  
 }  
 ​  
 int main(){  
     cout << "假设求解 4 取模 3 的逆元" << endl;  
     int a = 4, b = 4, mod = 3;  
     cout << qmi(b, mod - 2, mod) << endl; //  
 }

法2 扩展欧几里得求解逆元

 ```cpp
#include
#include
using namespace std;
typedef long long LL;
​
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, y, x);
y -= a / b * x;
return d;
}
​
int main(){
int a, mod;
a = 4, mod = 3;
int x, y, d;
d = exgcd(a, mod, x, y);
if(d == 1){ // 保证互质才会有逆元
cout << "4 % 3 的逆元大小为" << endl;
cout << ((LL)x % mod + mod) % mod << endl; // 保证输出的逆元为正整数
}
else{
puts("不存在逆元");
}
}


#### c++的函数传递方式

##### 关于引用

引用是C++的一种特殊类型，它指向一个变量起别名，语法：**数据类型 &别名＝原名**

- **引用必须初始化**
- **引用在初始化后不可改变**

引用的本质：指针常量

 ```cpp
 void func(int& ref){  
     ref = 100;//自动转换为*ref=100  
 }  
 int main(){  
     int a = 20;  
     int& ref = a;  
     //自动转换为int* const ref=&a const修饰的是ref，所以指针指向不可改变，所以引用不可改变  
     ref = 20;//(内部发现ref是引用，自动转换为*ref=20)  
     cout << "a=" << a << endl;  
     cout << "ref=" << ref << endl;  
     func(a);  
     cout << "ref=" << ref << endl;  
 }

 输出：  
 a=20  
 ref=20  
 ref=100
值传递：在栈区开辟一块新的空间，不会改变实参的值

相当于形参只是对实参的备份，在程序执行完之后就销毁了，所以形参的改变不会对实参进行改变

 ```cpp
void swap(int a, int b){
int temp = b;
b = a;
a = temp;
}
int main(){
int a = 20;
int b = 10;
swap(a, b);
cout << "a=" << a << endl;
cout << "b=" << b << endl;
}

 输出：
a=20
b=10


##### 地址传递：函数的参数是指向原来变量的指针，也就是存储的是原变量的地址，两者存储同一块空间

这时候由于形参实参处于同一块存储空间，形参的改变会影响实参。

```cpp
 void swap(int*a, int*b){  
     int temp = *b;  
     *b = *a;  
     *a = temp;  
 }  
 int main(){  
     int a = 20;  
     int b = 10;  
     swap(&a, &b);  
     cout << "a=" << a << endl;  
     cout << "b=" << b << endl;  
 }

 输出：  
 a=10  
 b=20
引用传递：通过给变量起别名可以简化指针修改形参

本质上与地址传递是一样的，但在交换函数时候就不用解引用，因为编译器内部已经帮我们解引用完成。

 void swap(int&a, int&b){  
     int temp = b;  
     b = a;  
     a = temp;  
 }  
 int main(){  
     int a = 20;  
     int b = 10;  
     swap(a, b);  
     cout << "a=" << a << endl;  
     cout << "b=" << b << endl;   
 }

 输出：  
 a=10  
 b=20

例题 G 莫卡和魔法图案

23级算法 E1 G题
时间限制：2000ms 内存限制：65536kb

题目描述

莫卡设计了一种魔法图案，对于任意非负整数 k，一个 k 阶魔法图案的定义如下：

  • 一个 0 阶魔法图案为一个 1×1 仅包含一个黑色格子的网格图；
  • 对于 k>0，一个 k 阶魔法图案是一个 3^k×3^k 的网格图，网格图可以划分为 9 个 3^{k−1}×3^{k−1} 大小的子网格。其中中心子网格仅包含白色格子，其余 8 个子网格为 k−1 阶魔法图案。

对于给定的 n，请你输出 n 阶魔法图案。

输入

第一行包含一个正整数 n(0≤n≤6)，含义如题面所示。

输出

输出 3^n 行，表示 n 阶魔法图案。

第 i 行为一个长度为 3^n 且仅包含 "." 和 "#" 的字符串，其中第 j 个字符为 "#" 当且仅当该位置的为黑色格子， 为 "." 当且仅当该位置的为白色格子，

输入样例1

 1

输出样例1

 ###  
 #.#  
 ###

输入样例2

 2

输出样例2

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########
Built with MDFriday ❤️