隔了一段时间来做。。感觉又变菜了。。
A
题意
给定n，找到0到n中任意两个数的gcd最大值
题解
最大的gcd很显然就是n和n/2的gcd，看好奇偶性就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
printf("%d\n",n/2);
}
return 0;
}
|
B
题意
给2n个数 挑n-1对 让每一对的和作为一个元素 所有元素的gcd不为1
题解
乍看有点唬人 实际一想 每个元素都是偶数就可以解决问题了 所以就一直挑奇数挑到剩0个或1个或已经够n-1对 然后剩下的用偶数对补满即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
vector<int> cou[2];
for(int i=0;i<n*2;++i){
int tmp;
scanf("%d",&tmp);
cou[tmp%2].push_back(i+1);
}
int num=0;
for(int i=0;(i+1)<cou[1].size()&&num<(n-1);i+=2){
printf("%d %d\n",cou[1][i],cou[1][i+1]);
++num;
}
for(int i=0;num<(n-1);i+=2){
printf("%d %d\n",cou[0][i],cou[0][i+1]);
++num;
}
}
return 0;
}
|
C
题意
俩人玩游戏 从n开始 两种操作 减一或者除这个数的任意一个大于一的奇数因子 谁不能动了就输
题解
看了一下题解 我的思路是没问题的。。然而就是wa也不知道为啥。。
可以看出 1是必败态 2是必胜态 所有的奇数都是必胜态 因为可以除以自身 偶数里所有不含奇数因子的除2以外都是必败态 也就是2的n次方形式 因为只能减一操作 转移到必胜态 所以是必败态 而任何带有奇数因子且因子中2的个数大于1的都是必胜态 也很简单 直接除以所有奇数因子的积转移到必败态 形式为2*x x为一个质数的是必败态 因为两种操作都转移到必胜态 形式为2*x*x。。。的为必胜态 除到之前说的形式也就是一步转移能到必败态
然而不知道哪里写错了。。。好气哦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int prime[1000020];
vector<int> fpri;
void pre(){
prime[0]=prime[1]=1;
for(int i=2;i<1000000;++i){
if(!prime[i]){
for(int j=i*2;j<1000000;j+=i){
prime[j]=1;
}
}
}
for(int i=2;i<1000000;++i){
if(!prime[i]){
fpri.push_back(i);
}
}
}
int main(){
int T;
pre();
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int res=0;
if(n==1){
res=1;
}else if(n==2){
res=0;
}else if(n&1){
res=0;
}else{
int tmp=n/2;
if(tmp%2){
for(int i=0;i<fpri.size();++i){
if(tmp%fpri[i]==0){
if(tmp/fpri[i]==1){
res=1;
}
break;
}
}
}else{
while(tmp%2==0){
tmp/=2;
}
if(tmp==1){
res=1;
}
}
}
if(res){
printf("FastestFinger\n");
}else{
printf("Ashishgup\n");
}
}
return 0;
}
|
D
题意
。。困 懒得看了 就这样吧先。。