질문의 계산 모드 = 1,000,000,007

-2

솔루션의

http://codeforces.com/contest/615/problem/D 링크 아래 코드에서 http://codeforces.com/contest/615/submission/15260890

을 여기서 1은 1 모드에서 차감하는 이유를 이해 할 수없는 오전 모드에서 차감하는 이유 여기서 mod = 1000000007

ll d = 1; 
ll ans = 1; 
for (auto x : cnt) { 
    ll cnt = x.se; 
    ll p = x.fi; 
    ll fp = binPow(p, (cnt + 1) * cnt/2, MOD); 
    ans = binPow(ans, (cnt + 1), MOD) * binPow(fp, d, MOD) % MOD; 
    d = d * (x.se + 1) % (MOD - 1);//why ?? 
}

출처

2016-11-28 Shashi Kundan

이 코드가 수행해야 할 작업을 지정하지 않았으므로 그 누구도 그 중 하나를 알지 못할 것입니다. – CollinD

지금, 솔루션과 문제의 링크를 추가하십시오. –

Welcome to Stack Overflow! 질문하는 방법을 읽고 [mcve]를 만들 수 있습니다. 그렇게하면 우리가 당신을 도울 수 있습니다. – Katie

사실상 그렇듯이 코드가 문맥에서 벗어나지 않는 한, 페르마의 조금 정리 :

때마다 MOD는 10^9+7이기 때문에, 하나는 그

a^b == a^(b mod (MOD-1)) mod MOD.

로서에 의미

a^(MOD-1) == 1 mod MOD.

로 지수를 줄일 수 소수입니다 코드는 작업에 효율적입니다. n=m*p^e을 입력하십시오. 여기서 m은 다음과 같습니다. 소수는 p보다 작습니다.

각 요소에 대해 f은 m이고, 1*f, p*f, ^2*f,...,p^e*f은 n입니다. n의 모든 요소를 통해이 제품은 따라서 모든 요소 m의 f 이상

p^(0+1+2+...+e) * f^(e+1) = p^(e*(e+1)/2) * f^(e+1)

을 통해 제품입니다. 지금 재귀 소인수 그들의 다중성 목록에 적용 할 수있는 결합 식

ans = ans^(e+1) * p^(d*e*(e+1)/2) d = d*(e+1)

에 d 같은 요소의 개수 및 mans 결과로서 요소의 생성물을 씌우고.

출처

2016-11-28 16:17:21 LutzL

질문의 계산 모드 = 1,000,000,007

답변

관련 문제