A - Pseudoprime numbers /B - Raising Modulo Numbers
/E - Rightmost Digit /F - 人见人爱A^B
这几道题都是快速幂，还是很简单的快速幂,模版要套对哦
具体看代码吧
//A
#include<iostream>
#include<algorithm>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int a,p;
bool Judge(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0) return false;
}
return true;
}
ll Fastpower(ll base,ll power,ll mod){
ll result = 1;
while(power > 0){
if( power&1){
result = result * base % mod;
}
base=base*base%mod;
power>>=1;
}
return result;
}
int main()
{
ios;
while(cin>>p>>a&&p&&a){
if(Judge(p)){
cout<<"no"<<"\n";
}
else{
if(Fastpower(a,p,p)==a){
cout<<"yes"<<"\n";
}
else{
cout<<"no"<<"\n";
}
}
}
return 0;
}
//B
#include<iostream>
#include<algorithm>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
ll t,m,h,a,b;
ll fastpower(ll base,ll power,ll mod){
ll result = 1;
while(power > 0){
if(power & 1) result= result * base % mod;
power>>=1;
base=base*base%mod;
}
return result;
}
int main()
{
ios;
cin>>t;
while(t--){
cin>>m>>h;
ll sum=0;
while(h--){
cin>>a>>b;
sum+= fastpower(a,b,m);
}
cout<<sum % m <<"\n";
}
return 0;
}
//E
#include<iostream>
#include<algorithm>
#include<bitset>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int n,t;
ll fastpower(ll b , ll p){
ll r=1;
while(p){
if(p&1) r=r*b%10;
p>>=1;
b=b*b%10;
}
return r;
}
int main()
{
ios;
cin>>t;
while(t--){
cin>>n;
cout<<fastpower(n,n)<<"\n";
}
return 0;
}
//F
#include<iostream>
#include<algorithm>
#include<bitset>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int a,b;
ll fastpower(ll b , ll p){
ll r=1;
while(p){
if(p&1) r=r*b%1000;
p>>=1;
b=b*b%1000;
}
return r;
}
int main()
{
while(cin>>a>>b&&a&&b){
cout<<fastpower(a,b)<<"\n";
}
return 0;
}C - Key Set
从集合里拿出一个一，非空幂集=2^(n-1)-1，和和为奇数的加上一就成了偶数，和为偶数的就不加
所以答案就是2^(n-1)-1
#include<iostream>
#include<algorithm>
#include<bitset>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int a,b;
ll fastpower(ll b , ll p){
ll r=1;
while(p){
if(p&1) r=r*b%1000;
p>>=1;
b=b*b%1000;
}
return r;
}
int main()
{
while(cin>>a>>b&&a&&b){
cout<<fastpower(a,b)<<"\n";
}
return 0;
}D - Distribution money
简单模拟，按照题意打代码就行了
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int n,a[maxn];
int main()
{
int t,n,m,mi,i;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
m=-maxn;
mi=0;
for(i=1;i<=n;i++)
{
scanf("%d",&t);
a[t]++;
if(a[t]>m)
{
m=a[t];
mi=t;
}
}
if(m>n-m)
{
printf("%d\n",mi);
}
else
{
printf("-1\n");
}
}
}
G - Trailing Zeroes (III)
这道题看了题解才会，二分法，0的个数和2和5有关
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
LL find(LL n)
{
LL cnt=0;
while(n>=5)
{
cnt+=n/5;
n=n/5;
}
return cnt;
}
LL fun(LL n)
{
LL mind,left=0,right=500000000;
while(left<=right)
{
mind=(left+right)/2;
if(find(mind)>n)
{
right=mind-1;
}
else
left=mind+1;
}
right=right-(right%5);
if(find(right)==n)
return right;
else
return 0;
}
int main()
{
int t;
scanf("%d",&t);
int g=0;
while(t--)
{
++g;
LL n;
scanf("%lld",&n);
LL k=fun(n);
if(k!=0)
{
printf("Case %d: %lld\n",g,k);
}
else
{
printf("Case %d: ",g);
printf("impossible\n");
}
}
}H - Pie
这道题之前做过，也是用二分
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define pi acos(-1.0)
using namespace std;
double pie[10010];
bool cmp(double a,double b)
{
return a>b;
}
int main()
{
int t,n,f,r;
scanf("%d",&t);
while(t--)
{
int cnt;
double pm=0,sum=0;
scanf("%d%d",&n,&f);
f++;
for(int i=0;i<n;i++)
{
scanf("%d",&r);
pie[i]=pi*r*r;
sum+=pie[i];
if(pm<pie[i]) pm=pie[i];
}
double l=pm/f,r=sum/f,mid;
while(r-l>0.000001)
{
mid=(l+r)/2;
cnt=0;
for(int i=0;i<n;i++)
cnt+=(int)(pie[i]/mid);
if(cnt<f) r=mid;
else l=mid;
}
printf("%.4f\n",l);
}
return 0;
}I - Can you solve this equation?
这不是二分法找零点吗，高中就学过，
#include<bits/stdc++.h>
using namespace std;
double f(double x)
{
return 8*pow(x,4)+7*pow(x,3)+2*pow(x,2)+3*x+6;
}
double dao(int y,double l,double h)
{
//cout<<"y="<<y<<" l="<<l<<" h="<<h<<endl;
double mid=(l+h)/2;
if(h-l>=10e-7)
{
//cout<<"h-l="<<h-l<<" mid="<<mid<<" f(mid)="<<f(mid)<<endl;
if(f(mid)==y)
{
return mid;
}
if(f(mid)>y)
return dao(y,l,mid);
if(f(mid)<y)
return dao(y,mid,h);
}
return mid;
}
int main()
{
int n,y;
cin>>n;
while(n--)
{
cin>>y;
if(y<f(0)||y>f(100))
cout<<"No solution!"<<endl;
else
{ printf("%0.4lf\n",dao(y,0,100));
//cout<<dao(y,0,100);
}
}
return 0;
}J - Subsequence
尺取法
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,S;
int a[100000];
int sum[100000];
void solve()
{
int res=n+1;
int s=0,t=0,sum=0;
for(;;)
{
while(t<n&&sum<S)
{
sum+=a[t++];
}
if(sum<S)
break;
res=min(res,t-s);
sum-=a[s++];
}
if(res>n)
res=0;
printf("%d\n",res);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i,j;
scanf("%d%d",&n,&S);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
solve();
}
return 0;
} 
京公网安备 11010502036488号