目录

A.找新朋友

B.互质

C.约瑟夫问题

D.进制转换

E.整数求和式的计算

F.波兰表达式

G.合并队列

---

A.找新朋友

数论

本题考查：欧拉函数，欧拉筛

欧拉筛，简而言之就是，任何合数都为某一比祂小的质数的倍数，这样，我们在找到一个质数后，把祂的所有倍数都标记为合数，由此原理即可筛掉所有合数。

欧拉函数：φ(x)表示小于x的所有与x互质的数的个数。特别地，我们令φ(1) = 1

φ(x) = x * (1-1/k) = x/k * (k-1)  ,k为 x 的所有因数

#include<bits/stdc++.h>
using namespace std;
bool isprime[33010];
int eula[33010];
void eulaPrime(){
    int i,j;
    isprime[1]=1;
    for(int i=1;i<33010;i++){
        eula[i]=i;
    }
    for(int i=2;i<33010;i++){
        if(!isprime[i]){
            eula[i]=i-1;
            for(int j=i+i;j<33010;j+=i){
                isprime[j]=1;
                eula[j]/=i;
                eula[j]*=(i-1);
            }
        }
    }
}
int main(){
    int n;cin>>n;
    int num=0;
    eulaPrime();
    while(n--){
        cin>>num;
        cout<<eula[num]<<'\n';
    }
    return 0;
} 

B.互质

本题原理与上一题一样，区别是上一题考点是数据量大，故采用记忆化搜索。本题考点是数据大，这样就无需也无法开数组记录了，直接用公式算即可

#include<bits/stdc++.h> 
using namespace std;

int main(){
    long long n=1;
    while(1){
        cin>>n;
        if(n==0) break;
        long long ans=n;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                ans=ans/i*(i-1);
            }
            while(n%i==0){
                n/=i;
            }  
        }
        if(n>1){
            ans=ans/n*(n-1);
        }
        cout<<ans<<'\n';
    }
    return 0;
} 

C.约瑟夫问题

数据量小，直接模拟即可。now用来表示当前到第几个人，数组 a[i] 用来表示第 i 个人是否已出圈

#include<bits/stdc++.h> 
using namespace std;
const int MAXN = 1e8;
bool a[MAXN];
int main(){
	int n,m;cin>>n>>m;
	int cnt=0;
	int now=0;
	while(cnt<n-1){
		for(int i=1;i<=m;i++){
			while(a[(++now)%(n+1)+1]==1){
				if(now>n){
					now%=n;
				} 
			}
			if(now>n) now%=n;
			if(i==m){
				a[now]=1;
				cnt++;
				now++;
				if(now>n){
					now%=n;
				}
			}
		}
	}
	int i=1;
	while(a[i]==1){
		i++;
	}
	cout<<i;
	return 0;
} 

D.进制转换

板子题

#include<bits/stdc++.h> 
#pragma GCC optimize(2)
using namespace std;
const int MAXN = 1e8;
int char_int(char a){
	return ('0'<=a&&a<='9') ? a-'0' : a-'A'+10;
}
char int_char(int x){
	return (0<=x&&x<=9) ? x+'0' : x-10+'A'; 
} 
int num[40];

int main(){
	int x,m;
	cin>>x>>m;
	int len=0;
	while(x!=0){
		num[len++]=x%m;
		x/=m;
	}
	for(int i=len-1;i>=0;i--){
		cout<<int_char(num[i]);
	}
	return 0;
} 

E.整数求和式的计算

这个题结构比较简单，将字符串看成三部分，数，加号，数。在遇到加号之前都是第一个数，加号后是第二个数，分别处理即可

#include<bits/stdc++.h> 
#pragma GCC optimize(2)
using namespace std;
const int MAXN = 1e8;
string s;
int main(){
	cin>>s;
	cout<<s;
	int a=0,b=0;
	char k;
	int i=0;
	while(s[i]>='0'&&s[i]<='9'){
		a=a*10+s[i]-'0';
		i++;
	}
	k=s[i++];      //后来才发现只有加法
	while(s[i]>='0'&&s[i]<='9'){
		b=b*10+s[i]-'0';
		i++;
	}
	cout<<a+b;
	return 0;
} 

F.波兰表达式

波兰表达式可以从前向后求值也可以从后向前求值，从后向前一般用栈，从前向后用递推。从后向前非常 不好操作，一般用递推的方法。

atof ：将字符数组转为double。类似的还有：

cin.getline(a,10)    //用于字符数组的输入，可以接收空格.当输入结束或者输入满9个字符时结束输入(因为要留一个\0)
getline(cin,s)       //处理含空格的字符串输入
atoi(a)              //将字符数组a转化为整形数据，支持负数
stoi(s)              //将字符串转化为整形数据，支持负数（而且输入+123会直接忽略+，非常智能!!）
to_string(k)         //把k(int,double,float型)转化为string.float和double均保留六位小数，不足用0补齐
s.find( ‘ch’ )       //在字符串s中查找’ch‘,返回ch中第一个字符的下标，若未找到则返回-1
s.substr( a , b )    //从下标为a的位置开始切，切出长度为b的字符串。不加b默认切到末尾
                     //记得在使用前判断切的长度是否大于字符串本身长度
putchar( 10 )        //换行符
reverse(s.begin() , s.end())  //反转字符

 本题样例：先遇到 ‘*’ , 运行两次 dp 函数，第一个dp 又遇到了 ‘+’ ，又进行两次dp，这两个dp处理11.0和12.0，操作是 ‘+’。然后进行第二个dp，过程和第一个dp差不多。最后，这两个dp函数返回给最初的dp，进行相乘操作，最终得出结果。

#include<bits/stdc++.h>
using namespace std;
double dp()
{
    char a[30];
    cin>>a;
    switch (a[0]){
    case '+':return dp() + dp();
    case '-':return dp() - dp();
    case '*':return dp()*dp();
    case '/':return dp() / dp();
    default:return atof(a); //atof函数能将char转换为double
    }
}
int main()
{
    printf("%.6f",dp());
}

G.合并队列

数据量较小，直接用sort即可

#include<bits/stdc++.h>
using namespace std;
int a[10000010];
int main(){
    int n;cin>>n;
    for(int i=1;i<=2*n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+2*n);
    for(int i=1;i<=2*n;i++){
        cout<<a[i]<<' ';
    }
}