这是一道简单的思维题,如果你想到了的话会很简单。
首先n的范围是7e4,如果简单地使用两个for循环进行遍历,肯定会超时。
这道题的思路:
直接找开完根的i和开完根的j,因为i*j<=n,且i,j为正整数,所以开完根的i和j都不超过sqrt(n),这样进行两次for循环找的话,时间复杂度就不会超时了。
然后如果开完根的i和开完根的j不相等,那么ans+=2,因为两者是可以交换的,算两种,反之,如果相等,ans++就可以了。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
int main()
{
int n,ans=0;
cin >> n;
for(int i=1;i<=sqrt(n);i++)
{
int k=i*i;
for(int j=1;j<=sqrt(k);j++)
{
if(i==j) ans++;
else if(k%j==0) ans+=2;
}
}
cout << ans << endl;
return 0;
}


京公网安备 11010502036488号