2019年安徽大学ACM/ICPC实验室新生赛
A.素数分布函数\pi (n)π(n)表示小于或等于n的素数的数目。例如\pi (10)=4π(10)=4（2,3,5,7是素数）。这个函数涉及到许多高等数论的内容，甚至和黎曼猜想挂钩，目前还有很多数学家正在不断探索其中的奥秘。千里之行始于足下，现在你开始关心一个问题：在正整数域中素数的分布是怎么样的。为了探索这个问题，你需要计算出一些\pi (n)π(n)的值。
题意：就是给你一个数N，然后让你求的在这个数之内的所有的素数个数！
1不是素数，素数的定义是除了1和本身，不能被其他数整除的数
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n) {//判断是否为素数
int i;
for(i = 2; i <= sqrt(n); i++) {
if((n % i) == 0)
return false;
}
return true; // 是素数
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int sum = 0;
for(int i=2;i<=n;i++){//就从2到N所有的数循环一下判断
if(isPrime(i))
sum++;
}
cout<<sum<<endl;
}
return 0;
}B. 众所周知，ICPC是一项团队赛事，需要三人合力协作完成。比赛的主办方会向参赛选手发放参赛服和食物，为了有备无患，准备的食物总是比参赛选手的总数要多一些。 假设你是一名ICPC教练，现在正带队参加一场ICPC区域赛。因为你们是最后一支注册的队伍而准备的食物还有剩余，因此你的队伍得到了4份食物（教练的食物是单独计算的）。因为工作人员的疏忽，每一份食物的分量不是均等的。如果恰好每人分到一份食物，那么没有人会抱怨。但现在多出了一份食物，所以你的队员希望每个人分到的食物分量是均等的。 一份食物只能被分给一个人，同时为了节约粮食，你不能浪费食物。如果没有方法把这四份食物分给三名队员并不使队员们产生抱怨，你只能将这份食物捐赠给慈善机构。 请判断是否存在一种方法可以将四份食物分给三名队员，每人获得的食物分量相等。
思路：一开始想错了，因为四分食物，若想分配成功的话，必须是两份相同并且大于其余两份，并且其余两份相加等于他俩其中之一。然后用了set<>,其实完全没有必要，搞清楚限制条件，排个序的话小的两个相加等于大的相等的其中之一就行了。（也就是sum%3 == 0）有这两个限制条件，必然能得出正确答案！
#include<bits/stdc++.h>
using namespace std;
int main(){
int T,i,n,m;
int a[10];
int temp;
cin>>T;
while(T--){
int sum=0;temp=0;
for(i=0;i<4;i++){
cin>>a[i];
sum+=a[i];
}
sort(a,a+4);
if(a[3]==(a[0]+a[1])){
temp=1;
}
if(sum%3==0&&temp==1){
cout<<sum/3<<endl;
}else{
cout<<"-1"<<endl;
}
}
return 0;
}C. 题意：就是能从从序列中找到N和子序列AHUICPC，一眼看去，数据特别小，只有10，所以我们能打表
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n;
cin>>n;
char a='A',b='H',c='U',d='I',e='C',f='P',g='C';
if(n==1)
cout<<a<<b<<c<<d<<e<<f<<g<<endl;
else if(n==2)
cout<<a<<b<<c<<d<<d<<e<<f<<g<<endl;
else if(n==3)
cout<<a<<b<<c<<d<<d<<d<<e<<f<<g<<endl;
else if(n==4)
cout<<a<<b<<c<<d<<d<<d<<d<<e<<f<<g<<endl;
else if(n==5)
cout<<a<<b<<c<<d<<d<<d<<d<<d<<e<<f<<g<<endl;
else if(n==6)
cout<<a<<b<<c<<d<<d<<d<<d<<d<<d<<e<<f<<g<<endl;
else if(n==7)
cout<<a<<b<<c<<d<<d<<d<<d<<d<<d<<d<<e<<f<<g<<endl;
else if(n==8)
cout<<a<<b<<c<<d<<d<<d<<d<<d<<d<<d<<d<<e<<f<<g<<endl;
else if(n==9)
cout<<a<<b<<c<<d<<d<<d<<d<<d<<d<<d<<d<<d<<e<<f<<g<<endl;
else if(n==10)
cout<<a<<a<<b<<c<<d<<d<<d<<d<<d<<e<<f<<g<<endl;
}除去偷懒的方法，我们还可以这样来做
#include<iostream>
#define maxn 1000000000+10
using namespace std;
long long arr[maxn]={0};
int brr[maxn]={0};
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
if(n<10)
{
cout<<"AHU";
for(int i=0;i<n;i++)
{
cout<<"I";
}
cout<<"CPC"<<endl;
}
else
{
for(int i=0;i<5;i++)
{
cout<<"A";
}
cout<<"HUICPC";
cout<<"C"<<endl;
}
}然后我就直接看了hard Version.数据范围变成1e9了.这样的话，打表可行不通了~
#include<iostream>
#include<bits/stdc++.h>
#include <algorithm>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
#include<string>
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
const int maxn=5e4;
const int MOD=998244353;
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int k=n/maxn;
int rem=n%maxn;
for(int i=1;i<=rem;i++) printf("A");
printf("H");
if(k) for(int i=1;i<=maxn-rem;i++) printf("A");
for(int i=1;i<=k;i++) printf("H");
printf("UICPC\n");
}
}D.这个题，俺是快乐了，上去直接20秒交一发 鹅哈哈哈！~~果然不对，在我意料之中！
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
cout<<y<<" "<<x<<" "<<x*y<<endl;
}
return 0;
}那么仔细的想一下啊，这个题如果X,Y两个数的GCD如果是1的话，那么就可以直接得知输出像俺上面的一样。其实这个道理很容易想清楚，因为X,Y，是由A,B，得来的，如果X，Y,的最大公约数不为1，那么Cmin是还有更小的呢！！！所以要想有A,B，那么X,Y,的最大公约数必须为1.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
long long x,y,m;
for(int i=0;i<n;i++)
{
scanf("%lld%lld",&x,&y);
m=__gcd(x,y);
if(m==1)
{
printf("%lld %lld %lld\n",y,x,x*y);
}
else
printf("-1\n");
}
return 0;
}E. 题意：就是每次把数字相加得到一个新的数字，然后在把新的数的各位数字相加，在得到一个新的数字，直至这个数字只有一位，然后求这些数的最小的一个数（要么都能被这个数整除，要么都不能被这个数整除）
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
string s;
while(T--){
cin>>s;
int sum = 0;
int flag = 0;
for(int i=0;i<s.length();i++)
sum = sum +s[i] - '0';
if((s[s.length()-1]-'0')%2==1) flag++;//判断始数是否为奇数
int res = 1;
while(sum >= 10){//就是得到每个数的所有位置加起来的数，并进行判断；
if(sum % 2 == 1)//先判断第二次得到的数是否为奇数，然后3，4，5...
flag++;
int h = sum;
sum = 0;
while(h>0){//每次得到新的一个数
sum = sum + h % 10;
h = h / 10;
}
res++;
}
if(sum % 2==1) flag++;//这个用来判断最后的那个数
if(flag==0||flag==res+1)//等于0表示都不能被2整除，相等表示都能被整出;
cout<<'2'<<endl;
else
cout<<'3'<<endl;
}
return 0;
}蕊蕊今年五岁了，她是一个爱上学的好孩子，每天都要乘坐公交车去上学。可是今天在等车上学时，一个问题难倒了她，你能帮可爱的蕊蕊解决这个问题吗？
假设有一路公交，该路公交车每班车的发车间隔并不确定，该公交车的发车间隔有50%的概率是a分钟发出下一辆，有50%的概率是b分钟发出下一辆。每次车到站时都会接走所有的乘客。
现在蕊蕊到家楼下的车站坐车，假设公交车的行驶速度完全相同，且路上没有堵塞，又假设每分钟有一名乘客到达车站等车。那请问当蕊蕊上车时，乘客排队的平均队伍长度是多少
这个题啊，十分巧妙！！！
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
double x,y;
while(cin>>x>>y)
{
printf("%.2lf",((x*x)+(y*y))/(x+y));
}
return 0;
}恭喜你，勇士。如果你过关斩将来到了这一题面前，那么说明你具有非凡的才华。现在你将面临最终的考验，为了对抗最后也是最强大的敌人，你需要组建一支属于你自己的军队。 你将组建一支魔法军队。一开始只有一名士兵，但是每次你可以使用两种法术来扩大你的军队的规模。 A: 消耗2点法力值将你的军队规模翻倍，这意味着你的军队规模将会从k扩大至2k——增加了k名士兵。 B: 如果你之前使用过法术，那么你可以消耗1点法力值重现你上一次法术的效果。这意味着如果上一次使用法术时你的军队规模增加了k，那么你的军队会再增加k名士兵。 虽然你现在拥有无比强大的法力，但这并不意味着可以随便浪费——毕竟你不知道你最后的敌人究竟有多么强大。事实上你希望消耗最少的法力值就能让你的军队的规模达到n(n \le 10^{14})n(n≤10 14 )。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dfs(ll n){
if(n==1){
return 0;
}
ll k;
for(k=2;k<=n/k;k++){
if(n%k==0){
break;
}
}
if(k<=n/k){
return k+dfs(n/k);
}
else{
return n;
}
}
int main(){
ll n;
cin>>n;
cout<<dfs(n);
}或者这样来写~~
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n, cnt = 0;
long long k;
string h,c;
while(cin>>n)
{
long long ans=0;
for(long long i=2;i*i<=n;++i)
{
while(n%i==0) ans+=i,n/=i;
}
if(n>1)
ans+=n;
printf("%lld\n",ans);
}
return 0;
}以上是大佬们的做法，俺真心没看懂~看俺的长的吧，易懂
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7+10;
bool st[maxn];
int prime[maxn];
ll n,cnt=0;
void get_prime()
{
for(int i = 2; i <= maxn; i++)
{
//在以前的循环中没有被标记，说明是质数
if(!st[i])prime[++cnt]=i;
for(int j = 1; prime[j]*i<=maxn;j++)
{
//标记合数
st[i*prime[j]]=true;
//j是i的最小质因数，则不再需要进行循环，避免重复标记
if(i%prime[j]==0)break;
}
}
}
int main()
{
ll ans=0;
get_prime();
scanf("%lld",&n);
for(int i = 1; n>1&&i<=cnt; i++)
{
if(n%prime[i]==0)
{
while(n%prime[i]==0)
{
ans+=prime[i];
n/=prime[i];
}
}
}
if(n>1)ans+=n;
printf("%lld\n",ans);
}