一道水题怎么也过不了，经历了痛苦且漫长的debug后发现竟然是数据类型没统一导致的。
题目: hdu5019
问题代码：
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
| #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5;
ll s[N];
ll a,b,k;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
cin>>a>>b>>k;
ll d=gcd(a,b);
int cnt=0,i;
for(i=1;i*i<d;i++)
{
if(d%i==0)
{
s[++cnt]=i;
s[++cnt]=d/i;
}
}
if(i*i==d)
s[++cnt]=i;
if(cnt<k)
{
cout<<-1<<'\n';
}
else
{
sort(s+1,s+cnt+1);
cout<<s[cnt+1-k]<<'\n';
}
}
return 0;
}
|
AC代码:
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
| #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5;
ll s[N];
ll a,b,k;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
cin>>a>>b>>k;
ll d=gcd(a,b);
ll cnt=0,i;
for(i=1;i*i<d;i++)
{
if(d%i==0)
{
s[++cnt]=i;
s[++cnt]=d/i;
}
}
if(i*i==d)
s[++cnt]=i;
if(cnt<k)
{
cout<<-1<<'\n';
}
else
{
sort(s+1,s+cnt+1);
cout<<s[cnt+1-k]<<'\n';
}
}
return 0;
}
|
唯一的不同的是cnt和i的数据类型，我感觉是在for循环的判定条件中有i*i<d，d是long
long类型的，左边i也得是long
long类型的才能快速判断，不然可能会在每次判断时都进行类型转换，造成大量时间的浪费。
一次TLE，发现了个很深的代码习惯问题。