01循环算法

1.求小数点的某一位，且超出float和double的精度问题

【题目描述】

分数a/b化为小数后，小数点后第n位的数字是多少？

【输入】

三个正整数a，b，n，相邻两个数之间用单个空格隔开。0<a<b<100，1<=n<=100000

【输出】

一个数字。

【输入样例】

1 2 1

【输出样例】

5

float精度

大约6-7位

double精度

大约15-16位

本题精度超过double

#include <iostream>

using namespace std;

int main(){
    int n,a,b;
    cin>>a>>b>>n;
    for(int i=1;i<=n;i++) {
        a = a % b;
        a = a * 10;
    }
    cout<<a/b<<endl;
    return 0;
}

2.幂的尾数

模运算的性质、同余、线性同余方程组、扩展欧几里得、逆元、费马小定理、中国剩余定理

模运算的性质：加、减、乘、乘方

性质1：(a+b)%m=(a%m+b%m)%m

性质2：(a-b)%m=(a%m-b%m)%m

性质3：(a* b)%m=(a% m* b%m)%m

性质4：(a^b)%m 循环性质3

算法思想：

* 用到了模运算的性质
* (a^b)%m计算很可能a^b就越界了
* 所以把它看成1*a*a*a*a*a……*a 总共有b个a
* 已知(a*b)%m=(a%m*b%m)%m
* 所以(a^b)%m=循环--> s=(s%m+a%m)%m这个语句一直循环b次

void text01(){
    int a,b,s=1;
    cin>>a>>b;
    /*
     * 用到了模运算的性质
     * (a^b)%m计算很可能a^b就越界了
     * 所以把它看成1*a*a*a*a*a……*a 总共有b个a
     * 已知(a*b)%m=(a%m*b%m)%m
     * 所以(a^b)%m=循环--> s=(s%m+a%m)%m这个语句一直循环b次
     * */
    for(int i=1;i<=b;i++){
        s=(s%m*a%m)%m;
    }
    printf("%03d",s);
}

什么时候用到模运算性质

当题目中是一个大数据量让你求末多少位的时候，一般要考虑模运算的性质

注意：pow的返回值位double类型，而模运算两边必须是整数类型

格式输出:

printf("%03d",3)

%0md–>宽度位m 不足m位前面补0

3.text段、data段、bss段

代码段(text段)

程序中的可执行部分，是由函数堆叠而成的

数据段(data段)

存放的是非零的全局变量和静态局部变量

ZI段(bss段)

zero initial 初始化位0的字段
存放的是为另的全局变量

在全局区开整形数组的最大容量为1e8左右

4.STL-标准模板库

容器

vector

list

stack

queue

priority_queue

set

map

unorder_set

unorder_map

迭代器

容器与算法之间的粘合剂

算法

max_element()

min_element()

sort()

可以引入头文件

#include <algorithm>

sort()算法

参1：待排序区间首元素的地址

参2：待排序区间为元素地址的下一位

参3：比较器/比较规则，默认缺省时，则针对C++已有数据类型进行升序排序

若此时数据是自定义的数据类型或者需要改写排序规则的话，需要重写参3

STL中所有传参为区间形式的函数，区间都应该遵循左闭右开原则

底层是快排–>O(nlogn)

#pragma once
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e8+10;
int nums[N],n;
bool cmp(int left,int right){//回调函数充当排序规则
    return left>right;
}
void text01(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>nums[i];
    }
    sort(nums+1,nums+n+1,cmp);
    for(int i=1;i<=n;i++){
        cout<<nums[i]<<" ";
    }
}

5.素数

法一：试除法

#pragma once
#include <iostream>
#include <algorithm>
using namespace std;
bool IsPrime(int x){
    for(int i=2;i*i<=x;i++){//若根号前没有因子，根号后也一定没有因子了
        if(x%i==0) return false;
    }
    return true;
}
void text01(){
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        if(IsPrime(i)){
            cout<<i<<" ";
        }
    }
}

法二：埃式筛法

素数的倍数一定不是素数，筛掉

#pragma once
#include <iostream>
#include <algorithm>

using namespace std;
const int N=1e3+10;
bool vis[N];//bool类型的标记数组
int prime[N],n,k;//prime数组
void E_sieve(){
    fill(vis+2,vis+n+1,1);
    for(int i=2;i<=n;i++){
        if(vis[i]){//开始筛选
            prime[++k]=i;//存入素数表
            for(int j=i*i;j<=n;j=j+i){
                vis[j]=false;
            }
        }
    }
}
void text01(){
    cin>>n;
    E_sieve();
    for(int i=1;i<=k;i++){
        cout<<prime[i]<<" ";
    }
}

6.整数去重

#pragma once
#include <iostream>
#include <algorithm>

using namespace std;
const int N=5e3+10;
int ct[N],x,n;
void text01(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(!ct[x]) cout<<x<<" ";
        ct[x]++;
    }
}