【BZOJ2705】【SDOI2012】Longge的问题

又是一道gcd题。。这题的欧拉函数貌似要暴力求。。

本来想把素数先筛出来的不过发现还慢些。。

那就暴力来吧。。复杂度不明然而跑得很快

// <2705.cpp> - 06/29/16 18:49:02
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
lol gl(){
    lol res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=7e4;
const int INF=1e9;
lol lim;
lol phi(lol x){
    lol res=x;
    for(int i=2;i<=lim&&i<=x;i++){
        if(x%i)continue;
        res=res/i*(i-1);
        while(!(x%i))x/=i;
    }
    if(x>1)res=res/x*(x-1);
    return res;
}
int main(){
    lol n=gl(),ans=0;lim=sqrt(n);
    for(lol i=1;i<=lim;i++){
        if(n%i)continue;
        ans+=i*phi(n/i);
        ans+=n/i*phi(i);
    }
    if(lim*lim==n)ans-=lim*phi(lim);
    printf("%lld",ans);
    return 0;
}

// <2705.cpp> - 06/29/16 18:49:02

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

lol gl(){

lol res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=7e4;

const int INF=1e9;

lol lim;

lol phi(lol x){

lol res=x;

for(int i=2;i<=lim&&i<=x;i++){

if(x%i)continue;

res=res/i*(i-1);

while(!(x%i))x/=i;

}

if(x>1)res=res/x*(x-1);

return res;

}

int main(){

lol n=gl(),ans=0;lim=sqrt(n);

for(lol i=1;i<=lim;i++){

if(n%i)continue;

ans+=i*phi(n/i);

ans+=n/i*phi(i);

}

if(lim*lim==n)ans-=lim*phi(lim);

printf("%lld",ans);

return 0;

}

说点什么