$RT.$ 蒟蒻求助

在这个题中

我一开始是这样写的：

#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
	int a;
	while(y!=0){
		a=x%y;
		x=y;
		y=a;
	}
	return x;
}
int main(){
	int sum=0;
	long long x,y,m;
	cin>>x>>y;
	m=x*y;
//	if(y<x){
//		cout<<0<<endl;
//		return 0;
//	}
	for(int i=2;i*i<=m;i++){
		if(y*x%i==0){
			if(i%x!=0||(m)/i%x!=0){
				continue;
			}
			if(gcd(i,m/i)==x){
				if(x==y){
					sum++;
				}
				else{
					sum+=2;
				}
//				cout<<i<<" "<<m/i<<endl;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}

结果$TLE$了

后来，我用$sqrt$:

#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
	int a;
	while(y!=0){
		a=x%y;
		x=y;
		y=a;
	}
	return x;
}
int main(){
	int sum=0;
	long long x,y;
	cin>>x>>y;
//	if(y<x){
//		cout<<0<<endl;
//		return 0;
//	}
	for(int i=2;i<=sqrt(y*x);i++){
		if(y*x%i==0){
			if(i%x!=0||(x*y)/i%x!=0){
				continue;
			}
			if(gcd(i,x*y/i)==x){
				if(x==y){
					sum++;
				}
				else{
					sum+=2;
				}
//				cout<<i<<" "<<x*y/i<<endl;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}

就$AC$了

所以$i*i$的时间复杂度是大于$sqrt$的吗？