第二题
标题：等差素数列
2,3,5,7,11,13,....是素数序列。
类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为30，长度为6。
2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。
这是数论领域一项惊人的成果！
有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：
长度为10的等差素数列，其公差最小值是多少？
注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。
//一开始想都没想，以为挨着的最小，结果gg,gg在越界
#include<cstdio>
#include<iostream>
using namespace std;
int primer[10000+10],mp,vis[100000+10];
//0为素数
int main()
{
int d;
for(int i=2; i<100000; i++)
if(!vis[i])
{
primer[mp++]=i;
for(int j=i*2; j<100000; j+=i)
vis[j]=1;
}
for(int i=1; i<mp; i++)
{
for(int k=i+1; k<mp; k++)
{
d=primer[k]-primer[i];
int j;
for(j=1; j<10; j++)
if(primer[i]+j*d>=100000||vis[primer[i]+j*d]) break;
if(j==10)
{
cout<<d<<endl;
return 0;
}
}
}
return 0;
}
第10题
标题： k倍区间
给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出
-----
输出一个整数，代表K倍区间的数目。
例如，
输入：
5 2
1
2
3
4
5
程序应该输出：
6
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
//其实从题目数据的大小中也可以获取大量的数据的
//一般的，我们可以把1到i之间的数据之和为s[i],则可枚举区间和，这样就会爆时间
//故在计算区间和时进行一些处理,如果(s[j]-s[i])%k==0,则是s[j]%k==s[i]%k,
//那么就是计算1到i(i位1到n)区间和中%k后相等的对数,于是时间复杂度变成了n+k,666啊
#include<cstdio>
#include<iostream>
using namespace std;
const int mx=100000+10;
int n,k,s[mx],t,vis[mx];
long long ans;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&t);
s[i]=(s[i-1]+t)%k;
vis[s[i]]++;
}
for(int i=0;i<k;i++)
if(vis[i])
ans+=vis[i]*(vis[i]-1)/2;
ans+=vis[0];
printf("%lld\n",ans);
return 0;
}
//优化了一下空间 #include<cstdio>#include<iostream>using namespace std;const int mx=100000+10;int n,k,st,t,vis[mx];long long ans;int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&t); st=(st+t)%k; vis[st]++; } for(int i=0;i<k;i++) if(vis[i]) ans+=vis[i]*(vis[i]-1)/2; ans+=vis[0]; printf("%lld\n",ans); return 0;}
第9题
标题： 分巧克力
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入：
2 10
6 5
5 6
样例输出：
2
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
//这个题目不用二分确实会超时,比赛的时候没有用二分，只是简单的优化了下
//二分的时间复杂度是logn*n
#include<cstdio>
#include<iostream>
using namespace std;
const int mx=100000+10;
int n,k,h[mx],w[mx];
bool solve(int t){
int s=0;
for(int i=1;i<=n;i++)
s+=(h[i]/t)*(w[i]/t);
if(s>=k) return true;
return false;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",h+i,w+i);
int left=1,right=100000;
while(left!=right){
int mid=(left+right)/2;
if(solve(mid)){
left=mid+1;
}
else
right=mid-1;
}
printf("%d\n",left);
return 0;
}
第8题
标题：包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
输出
----
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
例如，
输入：
2
4
5
程序应该输出：
6
再例如，
输入：
2
4
6
程序应该输出：
INF
样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
//仔细想了下，还真是扩展欧几里得的变形，如果所有数的最大公约数是1，则有有限，反之则有无限个
#include<cstdio>
#include<iostream>
using namespace std;
const int mx=11000,M=10000;
int g,dp[mx],n,a[mx],ans,mi=999999;
int gcd(int t,int tt){
if(tt==0) return t;
return gcd(tt,t%tt);
}
int main(int argc,char* argv[]){
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
dp[a[i]]=1;
mi=min(a[i],mi);
}
g=a[1];
for(int i=2;i<=n;i++)
g=gcd(g,a[i]);
if(g!=1){
puts("INF");
return 0;
}
int t=0;
for(int i=1;i<=M;i++){
if(dp[i])
{
for(int j=1;j<=n;j++)
dp[i+a[j]]=1;
t++;
if(t>=mi){
printf("%d\n",ans);
return 0;
}
}
else ans++,t=0;
}
return 0;
}