UVa 11582 거대 한 피 보 나치 수열
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=41990
해제
수학 문제 로 서 이것 은 비교적 흥미 로 운 것 입 니 다. 우선% n 의 의미 에서 피 보 나 치 는 순환 절 이 있 을 것 입 니 다. 이 순환 절 은 얼마 입 니까?두 개의 똑 같은 것 만 있 으 면 뒤에 계속 누 적 된 수열 도 똑 같 기 때문에 순환 절 이 나타 날 수 있 기 때문이다.n ^ 2 개의 서로 다른 두 개의 조합 이 있 기 때문에 n ^ 2 항 정도 에 반드시 순환 절 이 나타 날 것 입 니 다. 실측 n = 1000 이면 순환 절 은 1501 로 생각 보다 작 습 니 다.순환 절 을 찾 으 면% 가 됩 니 다. k = a ^ b% M (순환 절 길이) 은 빠 른 속도 로 남 습 니 다.계산 해서 f [k] 를 직접 출력 하면 됩 니 다.
데이터 형식 은 경상 입 니 다. 원래 int Pow (int a, ull p, int Mod) 를 썼 습 니 다. 제 가 생각 하 는 것 은 호출 할 때 int k = Pow (a% M, b, M) 를 썼 기 때 문 입 니 다. 분명히 a% M 은 매우 작 을 것 입 니 다. 그러나 저 는 a 입력 을 무시 할 때 unsigned long 형식 입 니 다. = int 를 강제로 만 들 면 신기 한 일이 생 길 수 있 습 니 다.(역시 취 했다).
또한 이 문제 의 데이터 그룹 수가 많 고 n 이 비교적 작다 면 n 에 대응 하 는 피 보 나치 수열 을 현 산 이 아니 라 미리 처리 해 야 한다.
코드 - -
#include
");return ;}
f[1]=1,f[2]=1;
for(int i=3;i<=n*n+10;i++)
{
f[i]=f[i-1]+f[i-2];f[i]%=n;
if(f[i]==f[2]&&f[i-1]==f[1]) {M=i-2;break;}
}
int k=pow(a%M,b,M);
printf("%d
",f[k]);
}
int main()
{
int T;cin>>T;
while(T--) solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
