bzoj 2671:Calc

リンク
　　http://www.lydsy.com/JudgeOnline/problem.php?id=2671
問題を解く
天よルッ!この問題はよく分かりますので、できるだけ短く話してください.条件を観察してみます.
(a+b)|ab(a+b)|a b
私たちの論ずる計算方法はすべて和です.
g c d g c dに関しては、必ず転送します.
g c d g c dにきてください.
d=gcd(a,b)d=g c d(a,b)
a=x d、b=yd a=x d、b=y dと書いて点数を書きます.
　　
x y d 2 d(x+y)x y d 2 d(x+y)
すなわち
xydx+y y x d+y
何故なら
g c d(x,y)=1 g c d(x,y)=1なので
g c d(x,x+y)=1 g c d(x,x+y)=1(明らかですね、公因法が出ないので)と同じです.
g c d(y,x+y)=1 g c d(y,x+y)=1なので
g c d(x y,x+y)=1 g c d(x y,x+y)=1なので、上式を整数にしたいなら、必ずあります.
(x＋y)|d(x＋y)|d.このような
dはいくつありますか?とりあえず結論を急がないでください.
⌊Nx+y⌋N x+y⌋個は、
dフォロー
x、y x、yは関連があります.
条件によっては以下の式が挙げられます.
　　
⎧;xd≦Nyd≦N x+y≦d｛x d≦N y≦N x+y≦d｝
三つ目の式を左右同乗する
y,得る
y(y+x)≦N y(y+x)≦N
に対する
x xの最小値は1ですので、
y(y+1)≦N y(y+1)≦N.
yは
N−−−−√Nレベルのものは、列挙することができる.
d≦⌊Ny⌋d≦⌊Ny⌋なので、dには上界があります.
では、答えを書きます.
　　
a n s=Σx=1 N√Σy=x+1 N√⌊Ny_;X+y_;[g c d(x,y)=1]a n=Σx=1 NΣy=x+1 N⌊N y⌊N y_;x+1 y(=8971 g)
この複雑さは安定しています.
O(NlogN)O(N l o g N)それです.
log l o gは求めます
g c d g c d時の複雑さ.実際の試験:TLE.
次に狂気じみた部分に入り、まずモビルスーツの反転を行います.
　　
Σx=1 N√Σy=x+1 N√⌊Ny_;x+y_;Σd gcd(x,y)μ(d)Σx=1 NΣy=x+1 N⌊N y_;x+y_;Σd d(x,y)μ (d)
　　
Σd=1 N√μ(d)Σx=1⌊N√d⌋Σy=x+1⌊N√d_;(xd+yd)⌋Σd=1 Nμ (d)Σx=1⌊Nd⌋Σy=x+1⌊N d⌊⌊N y d⌋(x d+y d)⌋
ここに注意してください.
x和
yはもう元のものではない.
x和
yになりました.
x d x dと
y d y dはそれぞれ以前のものに対応します.
x和
yです
　　
Σd=1 N√μ(d)Σx=1⌊N√d⌋Σy=x+1⌊N√d_;⌊Nyd2_;x+y⌋Σd=1 Nμ (d)Σx=1⌊Nd⌋Σy=x+1⌊N d⌊⌊N y 2⌋x+y𕹯
これはもとより少し早いです.複雑さはまだです.
O(N 1.5)O(N 1.5)は実際にTをテストしましたが、速度は確かに元のものより10倍近く速いです.(複雑さだけを見ても頼りにならない場合があります.)一番大きいデータを走るのは私のノートでは5 sしかないです.もう少し最適化すれば大丈夫です.
病気をなくす最適化について、一晩中自習したいと思いました.
s=x+y=x+y:
　　
Σd=1 N√μ(d)Σy=2⌊N√d⌋Σs=1+y 2−1⌊Nyd 2_;sΣd=1 Nμ (d)Σy=2⌊Nd⌋Σs=1+y 2 y−1⌊N y d 2⌋s
ブロック分け、複雑度が
O(N 1.25)O(N 1.25)は、この複雑さを見ないでください.定数はとても小さいです.真実の複雑さはこれよりもっと小さいはずです.でも、もうやめます.bzoj上1628 sで過ごしました.最大データは本機で0.4511 sだけ走ります.
コード

//       
#include 
#include 
#include 
#define maxn 50000
#define ll long long
using namespace std;
ll prime[maxn+10], mu[maxn+10], N, mark[maxn+10];
void init()
{
    ll i, j;
    mu[1]=1;
    for(i=2;i<=maxn;i++)
    {
        if(!mark[i])prime[++prime[0]]=i,mu[i]=-1;
        for(j=1;j<=prime[0] and i*prime[j]<=maxn;j++)
        {
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}
void work()
{
    ll ans=0, d, t, sqrtn=sqrt(N), tmp, y, last, s;
    for(d=1;d*(d+1)<=N;d++)
    {
        tmp=0;
        for(y=2;y<=sqrtn/d;y++)
        {
            t=N/(d*d*y);
            for(s=1+y;s<=y+y-1 and s<=t;s=last+1)
            {
                last=t/(t/s);
                tmp+=(min(last,y+y-1)-s+1)*(t/s);
            }
        }
        ans+=tmp*mu[d];
    }
    printf("%lld",ans);
}
int main()
{
    init();
    scanf("%lld",&N);
    work();
    return 0;
}