- A题题解：
快速幂加上素数判断，刚开始写的的素数判断用枚举，结果超时了，然后在网上找了一种方法。
（1）关于快速幂的一些想法：
快速幂模板中每乘一次就要模除m一下是因为可以减少计算量；
防止超出int或long long的范围；
比如计算(10010^2)%100可以直接计算10*10，10010大于的100部分对最后结果没有影响。
（2）判断素数
素数的分布规律
大于5的素数一定于6的倍数相邻,例如5和7,11和13,17和19等等。
证明
令 x ≥ 1,则大于5的自然数可以表示如下:
…6x-1, 6x, 6x+1, 6x+2, 6x+3, 6x+4, 6x+5,6(x+1)-1…
可以看到,不在6的倍数的两侧的6x+2, 6x+3, 6x+4,由于上式可表示为2(3x+1), 2(2x+3), 2(3x+2),So 他们一定不是素数,在除去6x本身,显然素数只能出现在6的倍数的两侧,但这只是素数的必要条件可不是充分必要条件,所以在6的倍数的两侧的数也不一定素数。
代码如下#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> typedef long long ll; using namespace std; ll a,p; /*bool ispri(ll p){ bool flag=true; int t=(int)sqrt((double)p); for(int i=2;i<p;i++){ if(p%i==0) { flag=false; break; } } return flag; }*/ bool ispri(ll n){ if(n==2||n==3) return 1; if(n%6!=1&&n%6!=5) return 0; for(int i=5;i<=floor(sqrt((double)n));i+=6) if(n%i==0||n%(i+2)==0) return 0; return 1; } ll poww(ll x,ll y,ll m){//(x^y)mod(m) ll ans=1; while(y){ if(y&1) ans=ans*x%m; x=x*x%m; y>>=1; } return ans; } int main(void){ while(scanf("%lld%lld",&p,&a)){ if(p==0&&a==0) break; if(ispri(p)) { printf("no\n"); continue;} if(poww(a,p,p)==a)printf("yes\n"); else printf("no\n"); } return 0; }B题题解：
依然是快速幂，#include<cstdio> #include<algorithm> #include<iostream> typedef long long ll; using namespace std; ll poww(ll x,ll y,ll m){//(x^y)mod(m) ll ans=1; while(y){ if(y&1) ans=ans*x%m; x=x*x%m; y>>=1; } return ans; } int main(void){ ll t; ll p,h,a,b; cin>>t; while(t--){ scanf("%lld%lld",&p,&h); ll ans=0; for(int i=0;i<h;i++){ scanf("%lld%lld",&a,&b); ans=ans+poww(a,b,p); } ans=ans%p; printf("%lld\n",ans); } return 0; }C题题解
利用排列组合可以知道集合的键集数量为2^(n-1)-1；#include<cstdio> #include<algorithm> #include<iostream> typedef long long ll; #define MOD 1000000007 using namespace std; ll poww(ll x,ll y,ll m){//(x^y)mod(m) ll ans=1; while(y){ if(y&1) ans=ans*x%m; x=x*x%m; y>>=1; } return ans; } int main(void){ int t; scanf("%d",&t); while(t--){ ll n; scanf("%lld",&n); n--; printf("%lld\n", poww(2,n,MOD)-1); } return 0; }D题题解
拿的钱x大于其他所有人拿的钱的和n-x，
即x>n/2;#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int a[10010]; int main(void){ int n,t; while(~scanf("%d",&n)){ int x=-1; memset(a,0,sizeof a); for(int i=0;i<n;i++){ scanf("%d",&t); a[t]++; } for(int i=0;i<10000;i++){ if(a[i]>n/2){ x=i; break; } } printf("%d\n",x); } return 0; }E题题解
快速幂模除10；#include<cstdio> #include<algorithm> #include<iostream> using namespace std ; typedef long long ll; ll poww(ll x,ll y,ll m){//(x^y)mod(m) ll ans=1; while(y){ if(y&1) ans=ans*x%m; x=x*x%m; y>>=1; } return ans; } using namespace std; int main(void){ int n; scanf("%d",&n); while(n--){ int x; scanf("%d",&x); printf("%d\n",poww(x,x,10)); } return 0; }F题题解：
快速幂模板#include<cstdio> #include<algorithm> #include<iostream> typedef long long ll; using namespace std; ll poww(ll x,ll y,ll m){//(x^y)mod(m) ll ans=1; while(y){ if(y&1) ans=ans*x%m; //printf("%lld %lld %lld\n",ans,x,y); x=x*x%m; y>>=1; } return ans; } int main(void){ ll n,m,t; while(scanf("%lld %lld",&n,&m)){ if(n==0&&m==0) break; ll ans=poww(n,m,1000); printf("%ld\n",ans);} return 0; }G题题解：
求乘阶中0的个数，其实就是求5的个数，
因为25=55，
125=55*5，
所以n中5的个数为n/5+n/25+n/125.....#include<cstdio> #include<algorithm> #include<iostream> using namespace std; const int maxn=5e8;//卡在数据大小上，痛苦； int zero; int check(int n){ int ans=0; while(n){ ans+=n/5; n/=5; } return ans; } int main(void){ int t; scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%d",&zero); int mid,s; int l=1,r=maxn; while(l<r){ mid=(l+r)/2; if(check(mid)>=zero) r=mid; else l=mid+1; } if(check(r)==zero) printf("Case %d: %d\n",i,r); else printf("Case %d: impossible\n",i); } return 0; }
H题题解：
求满足分配的最大尺寸：利用二分法，由于每个人的必须是完整的一块，所以不满足尺寸的需要抛弃，
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define PI 3.14159265359
using namespace std;
double a[10010];
const double esp=1e-6;//精确度
int main(void){
int n;
scanf("%d",&n);
double r;
while(n--){
memset(a,0,sizeof a);
int m,f;
double most=0.0;
scanf("%d %d",&m,&f);
f++;
for(int i=0;i<m;i++){
scanf("%lf",&r);
a[i]=r*r;
if(a[i]>most)most=a[i];
}
double l=0.0;
double r=most;
double mid;
while(r-l>esp){//实数不能直接比较与因为精度问题
mid=(r+l)/2;
int count_f=0;
for(int i=0;i<m;i++){
count_f+=(int)(a[i]/mid);//计算一块馅饼能分给几个人，舍弃不能分的馅饼
}
if(count_f<f)
r=mid; //mid过大
else
l=mid; //mid过小
}
printf("%.4f\n",mid*PI);
}
return 0;
}i题题解：
y必须满足f(0)<=y<=f(100);
浮点数不能直接比较，所以判断left和right的差值是不是趋近与0；
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
const double esp=1e-6;
using namespace std;
double check(double x){
//8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6
return 8*pow(x,4)+7*pow(x,3)+2*pow(x,2)+3.0*x+6.0;
}
int main(void){
int T;
double y;
scanf("%d",&T);
while(T--){
scanf("%lf",&y);
if(y<check(0)||y>check(100)){
printf("No solution!\n");
continue;
}
double r=100.0;
double l=0.0;
double mid;
while(r-l>esp){
mid=(r+l)/2.0;
if(check(mid) < y)l=mid;
else r=mid;
}
printf("%.4f\n",mid);
}
return 0;
}J题题解：
前缀和得到数列的和；然后从头开始枚举区间，利用lower_pound()函数计算最短区间：
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int a[100010]={0};
int n,m,x;
int main(void){
int t;
scanf("%d",&t);
int ans,s;
while(t--){
ans=100010;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
a[i]=a[i-1]+x;
}
for(int i=1;i<=n;i++){
s=m+a[i-1];
if(a[n]>s)
ans=min(lower_bound(a+i,a+n,s)-a-i+1,ans);
}
if(ans>n)
ans=0;
printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号