这是一道简单的思维题,如果你想到了的话会很简单。
首先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; }