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; }