hdu 4961 Boring Sum
제목 의 뜻 을 잘 이해 합 니 다. 실제로 바 꾸 면 b [i] 는 a [i] 앞의 첫 번 째 배수 입 니 다. 없 으 면 a [i], c [i] 는 a [i] 뒤의 첫 번 째 배수 입 니 다.
이렇게 하면 1 부터 100000 까지 모든 수의 약 수 를 미리 처리 하여 p [] 에 저장 하고 k [] 로 1 부터 100000 까지 각 수의 밀 착 배 수 를 표시 합 니 다.먼저 앞 뒤로 쓸 어 버 리 고 각 수의 약수 에 따라 k [] 를 업데이트 하고 b [] 를 얻 은 다음 에 뒤에서 c [] 를 얻 습 니 다.
코드:
#include <cstdio>
#include <iostream>
#include <vector>
#define MAX 100010
#include <cstring>
using namespace std;
int a[MAX];
int b[MAX];
int c[MAX];
int k[MAX];
bool vis[MAX];
vector <int > p[MAX];
int main(){
int n;
for(int i=1;i<=100000;i++){
for(int j=i;j<=100000;j+=i){
p[j].push_back(i);
}
}
while(~scanf("%d",&n),n){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
if(!vis[a[i]]) b[i]=a[i];
else b[i]=k[a[i]];
for(int j=0;j<p[a[i]].size();j++){
k[p[a[i]][j]]=a[i];
vis[p[a[i]][j]]=1;
}
}
memset(vis,0,sizeof(vis));
for(int i=n;i>=1;i--){
if(!vis[a[i]]) c[i]=a[i];
else c[i]=k[a[i]];
for(int j=0;j<p[a[i]].size();j++){
k[p[a[i]][j]]=a[i];
vis[p[a[i]][j]]=1;
}
}
long long res=0;
for(int i=1;i<=n;i++){
res+=(long long)b[i]*(long long)c[i];
}
printf("%I64d
",res);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
