数论
D - Together Square (atcoder.jp)
给你一个 \(n\) ,求有多少对 \((i,j)\) 满足 \(i∗j\) 是一个平方数, \(i,j\) 满足小于等于 \(n\) 。
思路:枚举 \(i\) ,看有多少 \(j\) 跟它相乘是平方数
分两种情况:
如果 \(i\) 是平方数,那么 \(j\) 必须是平方数。
如果 \(i\) 不是平方数:
找到最小的跟 \(i\) 相乘是平方数的 \(x\),怎么找这个数呢?
要用到质因数分解,比如 \(12600=2^3*3^2*5^2*7^1\),这显然不是一个平方数,要让它成为平方数
就要让次数为奇数的因子变成偶数,比如 \(12600\) 的 \(2\) 和 \(7\),也就是给它们各在分配一个,所以
\(12600*2*7\) 就是平方数,我们把 \(2*7\) 拿出来,那么这个数就是与 \(12600\) 相乘是平方数的最小数
所以 \(2*7\) 就算一个贡献,很容易直到还有 \(2*7*2^2,2*7*3^2,...,2*7*x^2\),这个数要小于 \(n\)
代码:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ll long long
ll n;
ll ans = 0;
void divid(int x)
{
int res = 1;
for (int i = 2; i*i <= x; i++)
{
if (x % i == 0)
{
int cnt = 0;
while (x % i == 0)
{
x /= i;
cnt++;
}
if (cnt % 2)
{
res *= i;
}
}
}
if (x > 1)
res *= x;//如果x还剩因子,那这个因子的次数一定是1,假设该因子是e,那么e*e>x,说明x只有一个e。
//cout << res << endl;
for (int i = 1; i * i * res <= n ; i++)
{
ans++;
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
divid(i);
}
cout << ans;
}
标签:平方,数论,ll,long,int,因子,12600
From: https://www.cnblogs.com/Jayint/p/16794706.html