【UVA 11426】[sum(gcd(i,j),1
1190 단어 onlinejudgeuva------올라 함수
sum(gcd(i,j), 1<=i1 구하기
아이디어:
1. 추이 관계를 구축한다. s(n)=s(n-1)+gcd(1,n)+gcd(2,n)+...+gcd(n-1,n);
2. f(n)=gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)를 설정합니다.
gcd(x, n)=i는 n의 약수(x
반면 gcd(x, n)=i는 gcd(x/i, n/i)=1과 같기 때문에 g(n, i)는phi(n/i)와 같다.phi(x)는 오라 함수다.
3. 시간의 복잡도를 낮춘다.체법으로phi[x]표를 미리 처리하다
역방향 사고방식은 체법으로 f(x)->매거인수를 미리 처리하고 그 모든 배수를 갱신하여 해답을 구한다.
코드:
#include
using namespace std;
typedef long long ll;
const int maxn=4100000;
ll f[maxn],s[maxn];
ll phi[maxn];//
void phi_table(int n)
{
memset(phi,0,sizeof(phi));
phi[1]=1;// 1
for(int i=2;i<=n;++i)if(!phi[i])//i （ ）
for(int j=i;j<=n;j+=i)// i
{
if(!phi[j])phi[j]=j;// j
phi[j]=phi[j]/i*(i-1);//
}
}
int main(){
phi_table(maxn);
memset(f,0,sizeof(f));
for(int i=1;i<=maxn;i++)
for(int j=i+i;j<=maxn;j+=i)//
f[j]+=i*phi[j/i];
memset(s,0,sizeof(s));
s[1]=0;
for(int i=2;i<=maxn;i++)
s[i]=s[i-1]+f[i];
int n;
while(scanf("%d",&n),n){
printf("%lld
",s[n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
AZ-900을 자택 수험으로 무료 취득한 이야기 (2020/10)에서 2일간(오전중에만)의 온라인 트레이닝을 받는 것으로 무료 바우처를 받을 수 있다(등록 메일에 온다) 때문에, 부터 Peason VUE でスケジュール 버튼을 눌러, 화면에 따라 예약해 합격합시다 . ※2020/1...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
