若一個數(shù)x是平方數(shù)，則d(x)為平方數(shù)

所以就是要考慮有多少對i*j為平方數(shù)

我們假設(shè)，i=p*k^2，那么，j=p*q^2時，i*j為平方數(shù)（p不含平方因子，k，q為正整數(shù)）

所以，我們對于一個i=p*k^2，對應(yīng)的j就有[√m/p]種

我們考慮快速求p，這樣對于所有k，i=p*k^2的答案都是一樣的，要么是1或-1

采用線性篩法，對于一個合法的p，我們可以篩掉p*k^2 ，這樣時間復(fù)雜度是就是線性的

#include<stdio.h> #include<math.h> #define N 10000000 #define L long long bool vis[10000020]={0}; L n,m,ans=0; int main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;++i)if(!vis[i]){int c=0;for(int j=1;i*j*j<=n;++j) vis[i*j*j]=1,++c;ans+=((int)sqrt(1.*m/i))&1?-c:c;}printf("%lld\n",ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/Extended-Ash/p/9477280.html

總結(jié)

以上是生活随笔為你收集整理的Jzoj4782 Math的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。