建设银行网站 诚聘英才 频道,二级网站都在一台服务器怎么做域名,营销微信管理,域名 和网站有什么区别若一个数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
