2018年全国多校算法寒假训练营练习比赛（第三场）

链接：https://www.nowcoder.net/acm/contest/75/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
夫夫有一天对一个数有多少位数感兴趣，但是他又不想跟凡夫俗子一样，
所以他想知道给一个整数n，求n！的在8进制下的位数是多少位。

输入描述:
第一行是一个整数t(0<t<=1000000)(表示t组数据)
接下来t行，每一行有一个整数n(0<=n<=10000000)
输出描述:
输出n！在8进制下的位数。
示例1
输入
3
4
2
5
输出
2
1
3

emmm，这题目斯特灵公式直接套，坑点在于题目卡时间。用cin超时，用scanf超时，用cout超时，必须要用scanf、printf！！！用scanf我能理解，难道printf速度也比cout快？？？

AC代码：

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define ll long long
 4 #define PI acos(-1)
 5 #define E 2.7182818284
 6 #define C log(8)
 7 #define tmp log(2*PI)
 8 using namespace std;
 9 int main(){
10     int t;
11     cin>>t;
12     while(t--){
13         int n;
14         scanf("%d",&n);
15         if(n==0) printf("1
");
16         else{
17             ll ans=(ll)(((log(n)+tmp)/2+n*log((double)n/E))/C);
18             printf("%lld
",ans+1);
19         }
20     }
21     return 0;
22 }

链接：https://www.nowcoder.net/acm/contest/75/B
来源：牛客网

一个小问题
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
uu遇到了一个小问题，可是他不想答。你能替他解决这个问题吗？
问题：给你k对a和r是否存在一个正整数x使每队a和r都满足：x mod a=r，求最小正解x或无解。

输入描述:
第一行是正整数k(k<=100000)
接下来k行，每行有俩个正整数a，r(100000>a>r>=0)
输出描述:
在每个测试用例输出非负整数m，占一行。
如果有多个可能的值，输出最小的值。
如果没有可能的值，则输出-1。
示例1
输入
2
8 7
11 9
输出
31

解题思路：中国剩余定理扩展。模板题

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define ll long long
 4 using namespace std;
 5 ll m[100000+100];
 6 ll r[100000+100];
 7 ll exgcd(ll a,ll b,ll & x,ll &y ){
 8     ll gcd,t;
 9     if(b==0){
10         x=1;
11         y=0;
12         return a;
13     }
14     gcd=exgcd(b,a%b,x,y);
15     t=x-a/b*y;
16     x=y;
17     y=t;
18     return gcd;
19 }
20 ll lcm(ll a,ll b,ll gcd){  //最小公倍数
21     return (a/gcd)*b;
22 }
23 int main(){
24     int t;
25     cin>>t;
26     for(int i=0;i<t;i++){
27         scanf("%d%d",m+i,r+i);
28     }
29     ll x,y;
30     bool flag=true;
31     for(int i=0;i<t-1;i++){
32         ll gcd=exgcd(m[i],m[i+1],x,y);
33         if((r[i+1]-r[i])%gcd!=0){   //判断是否有整数解
34             flag=false;
35             break;
36         }
37         ll t=m[i+1]/gcd;
38         x=((x*(r[i+1]-r[i])/gcd)%t+t)%t;
39         ll M=lcm(m[i],m[i+1],gcd);
40         ll R=(m[i]*x+r[i])%M;
41         m[i+1]=M;
42         r[i+1]=R;
43     }
44     if(!flag){
45         cout<<-1<<endl;
46     }else{
47         cout<<r[t-1]<<endl;
48     }
49     return 0;
50 }

View Code

链接：https://www.nowcoder.net/acm/contest/75/C
来源：牛客网

守护白起

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

最近古yu迷上了《恋与制作人》，天天嚷嚷着白起我老公(死gay死gay的),白起又向古yu提出了一个问题：
给你n种卡牌（数量无限）,将其摆成长度为m的圆环的方案数。

(如果这个环可以通过若干次旋转或者反方向读(（abc）(cba)是一样的),则认为他们是一样的)
这时古yu一脸茫然，大哭特苦不能守护白起了。古yu希望你能帮助他解决这个问题去守护白起。

输入描述:

第一行一个t(0<t<=500)
接下来t行，每行俩个正整数n,m(1<=n,m<=10000)

输出描述:

一个答案加换行(答案可能很大，所以取模1000000007)

示例1

输入

2
3 4
1 2

输出

21
1

说明

对于第一个样例有21种不同的方法
/ aaaa / aaab / aaac / aabb / aabc / aacc / abab /
/ abac / abbb / abbc / abcb / abcc / acac / acbc /
/ accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc



C题待解决。


链接：https://www.nowcoder.net/acm/contest/75/D
来源：牛客网

小牛vs小客

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小牛和小客玩石子游戏，他们用n个石子围成一圈，小牛和小客分别从其中取石子，谁先取完谁胜，每次可以从一圈中取一个或者相邻两个，每次都是小牛先取，请输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）（1 2 3 4 取走 2 13 不算相邻）

输入描述:

输入包括多组测试数据
每组测试数据一个n（1≤n≤1e9）

输出描述:

每组用一行输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）

示例1

输入

2
3

输出

XiaoNiu
XiaoKe

解题思路：博弈。n>=3小客胜。

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int main(  ){
 5     int n;
 6     while(cin>>n){
 7         if(n>=3) cout<<"XiaoKe"<<endl;
 8         else cout<<"XiaoNiu"<<endl;
 9     }
10     return 0;
11 }

链接：https://www.nowcoder.net/acm/contest/75/E
来源：牛客网

进击吧！阶乘

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给定一个整数N（0≤N≤10000），求取N的阶乘

输入描述:

多个测试数据，每个测试数据输入一个数N

输出描述:

每组用一行输出N的阶乘

示例1

输入

1
2
3

输出

1
2
6

解题思路：大数相乘。建议使用java，因为有现成的代码方法。c++较复杂些。

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define ll long long
 4 using namespace std;
 5 string Mult(string s,int x)  //大数乘以整形数
 6 {
 7     reverse(s.begin(),s.end());
 8     int cmp=0;
 9     for(int i=0;i<s.size();i++)
10     {
11         cmp=(s[i]-'0')*x+cmp;
12         s[i]=(cmp%10+'0');
13         cmp/=10;
14     }
15     while(cmp)
16     {
17         s+=(cmp%10+'0');
18         cmp/=10;
19     }
20     reverse(s.begin(),s.end());
21     return s;
22 }
23 int main(){
24     int n;
25     while(cin>>n){
26         if(n==0)cout<<"1"<<endl;
27         else{
28             string ans="1";
29             for(int i=1;i<=n;i++){
30                 ans=Mult(ans,i);
31             }
32             cout<<ans<<endl;
33         }
34     }
35     return 0;
36 }

链接：https://www.nowcoder.net/acm/contest/75/F
来源：牛客网
小牛再战
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
共有N堆石子，已知每堆中石子的数量，两个人轮流取石子，每次只能选择N堆石子中的一堆取一定数量的石子（最少取一个），取过子之后，还可以将该堆石子中剩余的石子随意选取几个放到其它的任意一堆或几堆上。等哪个人无法取子时就表示此人输掉了游戏。注意：一堆石子没有子之后，就不能再往此处放石子了。

假设每次都是小牛先取石子，并且游戏双方都绝对聪明，现在给你石子的堆数、每堆石子的数量，请判断出小牛能否获胜。

输入描述:
可能有多组测试数据(测试数据组数不超过1000)
每组测试数据的第一行是一个整数，表示N(1<=N<=10)
第二行是N个整数分别表示该堆石子中石子的数量。（每堆石子数目不超过100）
当输入的N为0时，表示输入结束
输出描述:
对于每组测试数据，输出Win表示小牛可以获胜，输出Lose表示小牛必然会败。
示例1
输入
3
2 1 3
2
1 1
0
输出
Win
Lose
备注:
提示：
例如：如果最开始有4堆石子，石子个数分别为3 1 4 2，而小牛想决定要先拿走第三堆石子中的两个石子（石子堆状态变为3 1 2 2），然后他可以使石子堆达到的状态有以下几种：
3 1 2 2（不再移动石子）
4 1 1 2（移动到第一堆一个）
3 2 1 2（移动到第二堆一个）
3 1 1 3（移动到第四堆一个）
5 1 0 2（全部移动到第一堆）
3 3 0 2（全部移动到第二堆）
3 1 0 4（全部移动到最后）

还是博弈题。有待解决


链接：https://www.nowcoder.net/acm/contest/75/G
来源：牛客网

大水题

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给出一个数n，求1到n中，有多少个数不是2 5 11 13的倍数。

输入描述:

本题有多组输入
每行一个数n，1<=n<=10^18.

输出描述:

每行输出输出不是2 5 11 13的倍数的数共有多少。

示例1

输入

输出

说明

1 3 7 9

解题思路：容斥定理。

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define ll long long
 4 using namespace std;
 5 int main(){
 6     ll n;
 7     while(cin>>n){
 8         ll a2=n/2;
 9         ll a5=n/5;
10         ll a11=n/11;
11         ll a13=n/13;
12         ll a25=n/10;
13         ll a211=n/22;
14         ll a213=n/26;
15         ll a511=n/55;
16         ll a513=n/65;
17         ll a1113=n/(11*13);
18         ll a2511=n/(2*5*11);
19         ll ans=a2+a5+a11+a13-a25-a211-a213-a511-a513-a1113+a2511+(n/(2*5*13))+(n/(2*11*13));
20         ans=ans+(n/(5*11*13))-(n/(2*5*11*13));
21         cout<<n-ans<<endl;
22     }
23     return 0;
24 }

链接：https://www.nowcoder.net/acm/contest/75/I
来源：牛客网

三角形

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给你一个三角形的顶点A,B,C的坐标（坐标都为整数），请求出三角形的面积，三角形内的点的个数以及边AB、BC和AC边上的点的个数（不包括顶点ABC）

输入描述:

多组输入
每组输入三行,每行两个整数
第一行顶点A的坐标Xa,Ya.
第二行顶点B的坐标Xb,Yb.
第三行顶点C的坐标Xc,Yc.
0<=X,Y<=1,000,000
输入-1结束输入

输出描述:

每组输出一行，输出一个实数（保留一位小数），四个整数，分别代表三角形面积，三角形内的点的个数以及边AB、BC和AC边上的点的个数，每个数用空格隔开。

示例1

输入

输出

2.0 0 1 1 1
4.5 1 2 2 2

说明

第一组图一，第二组图

解题思路：皮克公式应用。

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define ll long long
 4 using namespace std;
 5 struct Node{
 6     ll x,y;
 7 };
 8 double mult(Node t1,Node t2){
 9     return double(t1.x*t2.y-t1.y*t2.x);
10 }
11 ll gcd(ll a,ll b){
12     if(b==0) return a;
13     else return gcd(b,a%b);
14 }
15 int main(){
16     ll t;
17     while(cin>>t){
18         if(t==-1) break;
19         Node a,b,c;
20         a.x=t;
21         cin>>a.y>>b.x>>b.y>>c.x>>c.y;
22         double s=double(abs(mult(a,b)+mult(b,c)+mult(c,a))/2);
23         printf("%0.1f ",s);
24         ll ab=gcd((ll)abs(a.x-b.x),(ll)abs(a.y-b.y))-1;
25         ll bc=gcd((ll)abs(b.x-c.x),(ll)abs(b.y-c.y))-1;
26         ll ca=gcd((ll)abs(c.x-a.x),(ll)abs(c.y-a.y))-1;
27         ll ans=s+1-(ab+bc+ca+3)/2;
28         cout<<ans<<' '<<ab<<' '<<bc<<' '<<ca<<endl;
29     }
30     return 0;
31 }