D. A Simple Math Problem
1.题意
给定正整数a,b，求x,y满足x+y=a，lcm(x,y)=b。
2.题解
设c=gcd(x,y)，那么x=i*c，y=j*c。因为c是x,y的最大公约数，所以i,j互质。
所以a=x+y=(i*c)+(j*c)=(i+j)*c，b=lcm(x,y)=x*y/gcd(x,y)=x*y/c=(i*c*j*c)/c=i*j*c
由于i,j互质，所以i+j和i*j也互质，因此gcd(a,b)=c=gcd(x,y)
因为x+y=a x*y=b*gcd(x,y)=b*gcd(a,b)，解二元一次方程得：x=(a+sqrt(a*a-4*b*gcd(a,b)))/2
（参考题解：https://blog.csdn.net/Ivan_zcy/article/details/83213026）
3.代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll gcd(ll a,ll b){ 5 return b==0?a:gcd(b,a%b); 6 int main () { 7 ll a, b; 8 while(~scanf("%lld%lld",&a,&b)){ 9 ll c=gcd(a,b); //c=gcd(x,y)=gcd(a,b) 10 double x=(sqrt(a*a-4*b*c)+a)/2; 11 if(x==(ll)x){ 12 ll ans=(ll)x; 13 cout<<min(ans,a-ans)<<' '<<max(ans,a-ans)<<endl; 14 } 15 else 16 cout<<"No Solution"<<endl; 17 } 18 19 return 0; 20 }
H. To begin or not to begin
1.题意
一个盒子里有红色和黑色两种共n个球，只有一个红球，其余为k个黑球，两个人轮流从盒子里取球，先取出红球者获胜。如果第一个取球的人有优势输出1，劣势输出2，均势则输出0。
2.题解
设第一个人获胜概率为A，第二个人获胜概率为B。当k=1时，A=B=1/2，输出0；当k=2时，A=1/3+2/3*1/2=2/3，B=2/3*1/2=1/3，输出1；当k=3时，A=1/4+3/4*2/3*1/2=1/2，B=3/4*1/3+3/4*2/3*1/2=1/2······推得结论为：当k为奇数时，输出0，否则输出1。
3.代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int k; 4 int main(){ 5 ios::sync_with_stdio(false); 6 while(~scanf("%d",&k)){ 7 if(k%2) 8 cout<<0<<endl; 9 else 10 cout<<1<<endl; 11 } 12 13 return 0; 14 }
I. Convex
1.题意
给定n个点和点到n边形中心的距离，求n边形面积。
2.题解
将每个三角形面积相加即为n边形的面积。
3.代码
1 #include<bits/stdc++.h> 2 #define PI 3.1415926 3 using namespace std; 4 int n,d; 5 int main(){ 6 while(~scanf("%d%d",&n,&d)){ 7 int x; 8 double ans=0.0; 9 for(int i=1;i<=n;i++){ 10 cin>>x; 11 ans+=d*d*sin(PI*x/180)/2; 12 } 13 printf("%.3f ",ans); 14 } 15 16 return 0; 17 }
J. Find Small A
1.题意
给定n个数，每个数都可以拆开成一个32位的二进制，每八位一个字节 ，问每个字节的二进制数换算成十进制有多少个97。
2.题解
数字a%256就是取后八位，每八位判断一次。
（参考题解：https://blog.csdn.net/zzcblogs/article/details/71079356）
3.代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,ans; 4 int main() { 5 cin>>n; 6 for(int i=1;i<=n;i++){ 7 int x; 8 cin>>x; 9 while(x){ 10 if((x%256)==97) 11 ans++; 12 x/=256; 13 } 14 } 15 cout<<ans<<endl; 16 17 return 0; 18 }