hdu 4611
1556 단어 프로 그래 밍알고리즘바 이 두ACMhdu 다 교 리그
만약 두 수의 최소 공배수 가 비교적 클 때 (최대 999900000), 두루 구하 면 틀림없이 시간 을 초과 할 것 이다
그 당시 에 여러 가지 규칙 을 찾 으 려 고 했 지만 찾 지 못 했 습 니 다. 마지막 으로 저 는 옮 겨 다 니 는 최적화 가 생각 났 습 니 다. 바로 매번 한 개의 숫자 만 늘 리 는 것 이 아니 라
가장 큰 미 공 을 구 하 는 것 은 두 상자 의 번호 가 점점 증가 하 는 것 이다. 그러면 매번 첫 번 째 차 이 를 더 한 미 동반 만 필요 하 다.
공의 번호 에 미 를 더 하면 매번 1 을 더 하 는 것 보다 빠 르 고 옮 겨 다 니 는 구간 을 줄 일 것 이다.
그 결과 가장 큰 9999000 원 의 답 을 구 하 는 순간 나 와 자신 감 이 커 졌 고 결 과 는 몇 번 이나 틀 렸 다.
변 수 를 64 자리 로 바 꿀 생각 이 있 었 는데 예전 에 문 제 를 풀 때 이런 문제 가 있 었 습 니 다.
64 비트 와 int 혼합 연산 에 오류 가 발생 하면 수정 후 abs 함수 에 경고 가 있 으 면 다시 바 꿉 니 다.
폭력 이 나 온 결과 와 는 다른 몇 가지 답 이 있 었 다.
오늘 64 명 을 고치 면 A 가 됩 니 다. 그 후회,,,,,,,,,,,,,,,,,,,,,,,,,,,
#include <stdio.h>
#include <string.h>
__int64 gcd(__int64 a,__int64 b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
__int64 abs(__int64 a)
{
if(a>0)return a;
return -a;
}
__int64 cont(__int64 n,__int64 a,__int64 b)
{
__int64 ans,i,mi;
i=0;ans=0;
while(i<n)
{
mi=(a-i%a)>(b-i%b)?(b-i%b):(a-i%a);
if(i+mi>=n)
mi=n-i;
ans+=abs(i%a-i%b)*mi;
i+=mi;
}
return ans;
}
int main()
{
int T;
__int64 n,a,b,t;
__int64 ans;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&a,&b);
t=gcd(a,b);
t=a*b/t;
if (t>=n) ans=cont(n,a,b);
else ans=cont(t,a,b)*(n/t)+cont(n%t,a,b);
printf("%I64d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
