由前台有后台的网站怎么做,辽宁省大学生创新创业平台,京津冀协同发展的战略意义,网站开发费用无形资产若一个数x是平方数#xff0c;则d(x)为平方数 所以就是要考虑有多少对i*j为平方数 我们假设#xff0c;ip*k^2#xff0c;那么#xff0c;jp*q^2时#xff0c;i*j为平方数#xff08;p不含平方因子#xff0c;k#xff0c;q为正整数#xff09; 所以#xff0c;我们对… 若一个数x是平方数则d(x)为平方数 所以就是要考虑有多少对i*j为平方数 我们假设ip*k^2那么jp*q^2时i*j为平方数p不含平方因子kq为正整数 所以我们对于一个ip*k^2对应的j就有[√m/p]种 我们考虑快速求p这样对于所有kip*k^2的答案都是一样的要么是1或-1 采用线性筛法对于一个合法的p我们可以筛掉p*k^2 这样时间复杂度是就是线性的 #includestdio.h
#includemath.h
#define N 10000000
#define L long long
bool vis[10000020]{0};
L n,m,ans0;
int main(){scanf(%lld%lld,n,m);for(int i1;in;i)if(!vis[i]){int c0;for(int j1;i*j*jn;j) vis[i*j*j]1,c;ans((int)sqrt(1.*m/i))1?-c:c;}printf(%lld\n,ans);
} 转载于:https://www.cnblogs.com/Extended-Ash/p/9477280.html
