Enginuity Check+Express 幂+dp SRM 660 Div 2 Hard: Powerit
6095 단어 쾌속멱
Powerit
Problem Statement
You are given three ints: n, k, and m.
For each i between 1 and n, inclusive, Fox Ciel calculated the number i^(2^k - 1). ("^"denotes exponentiation.)
Return the sum of all numbers Fox Ciel calculated, modulo m.
Definition
ClassPowerit
Methodcalc
Parametersint , int , int
Returnsint
Method signatureint calc(int n, int k, int m)
(be sure your method is public)
Limits
Time limit (s)2.000
Memory limit (MB)256
Constraints
Test cases
n4
k1
m107
Returns
10
n4
k2
m107
Returns
100
We have
k=2 and therefore (2^
k - 1) = (2^2 - 1) = 3. Fox Ciel calculated the numbers 1^3, 2^3, 3^3, and 4^3. Their sum is 100, and 100 modulo 107 is 100.
n3
k3
m107
Returns
69
The actual sum of Ciel's numbers is 2316, and 2316 modulo 107 is 69.
n1
k400
m107
Returns
1
n10
k2
m10
Returns
5
문제풀이
Problems that ask you to return the result modulo 1,000,000,007 (or in this case an argument
m) usually do so to allow us to solve problems that have large results without actually using those large numbers in calculations. We can handle these numbers with modular arithmetic. Read this recipe for more info.
This problem has two parts. First we need to know that each element of the sum can be calculated in O(k) time. We have a power of the form i2k−1. If we use exponentiation by squaring, we can calculate a power in O(log(x)) time where x is the exponent. This time the exponent is O(2k) , the base 2 logarithm of 2k is k. This means that if we use exponentiation by squaring we will need O(k) time. Because the specific exponent is a power of 2 minus 1, there are also other methods we can use. For example: 2k−1=20+21+22+...2k−1. So we have: i20+21+22+...2k−1=(i20)(i21)(i22)...(i2k−1). Each i2k can be found by squaring i2k−1. Ultimately, it doesn't matter if we use this method that is specific to this problem because it is still O(k)
The second part of the problem is to realize that even with such an algorithm, we will need O(nk) time to find all n elements of the sum and add them together. For the constraints and the time limit that is too high, specially because of all the modulo operations we will need to do for each step.
If we want a faster solution we should try to look for a way to reuse the work spent in calculating the result for an i so that it can make the calculation for other elements easier. A nice way is to notice this: Imagine a number a=bc, a is the product of two integers. The exponentiation for a is : f(a)=a2k−1. Try this:
f(a)=a2k−1
f(a)=(bc)2k−1
f(a)=(b2k−1)(c2k−1)
f(a)=f(b)f(c)
Exponentiation is distributive between products. Since we have to calculate f(i) for all the numbers in a range, it is likely that when we are about to calculate f(a) we already know the values of f(b) and f(c) , so we can just reuse those results and avoid an O(k) calculation.
We just need to materialize that idea into a solution. For each i in the range we need to find two factors pq such that i=pq. We should tell right away that there will be many numbers for which this is impossible: Prime numbers. If i is prime, we need to use the past method of calculating f(i) in O(k) time. There are 78498 prime numbers among the first 1000000 natural numbers. So in the worst case we will do the O(k) algorithm 78498 times. It is still much better than doing it 1000000 times.
Finally, in case i is composite, we need to quickly find two factors pq=i. We can just do all of this as we test if i is prime, just use the successive divisions, if we don't find a divisor p (and therefore q=ip is also a divisor so we have our pair of factors), then the number is prime. We can do better and use a Sieve of Eratosthenes, just with a small modification, when you find a prime number p , don't just strike down its multiples as composite numbers, also save p as a "first factor"of each of the composite numbers. Then we can use the look up for the first factor to find a divisor.
long get_ith_element(int i, int k, int m)
{
// calculate i ^ (2^k - 1) in O(k) time:
long p = i;
long q = p;
for (int j = 1; j < k; j++) {
q = (q * q) % m;
p = (p * q) % m;
}
return p;
}
int calc(int n, int k, int m)
{
// modified Sieve of Erathostenes, when the number is composite,
// first_factor[i] will return a prime number that divides it.
vector first_factor(n + 1, 1);
for (int i = 2; i <= n; i++) {
if (first_factor[i] == 1) {
// prime
first_factor[i] = i;
for (int j = i+i; j <= n; j += i) {
first_factor[j] = i;
}
}
}
// f(p*q) = f(p) * f(q) , because f(i) = i ^ (something)
vector dp(n + 1, 1LL );
long sum = 0;
for (int i = 1; i <= n; i++) {
if (first_factor[i] == i) {
dp[i] = get_ith_element(i,k,m);
} else {
dp[i] = (dp[first_factor[i]] * dp[i / first_factor[i]]) % m;
}
sum += dp[i];
}
return (int)(sum % m);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
VIJOS 1477 펄럭이는 물방울팁: 1.이 문제의 폭력은 먼저 잘 써서 준비할 수 있어 항상 유용하다.2. T의 범위를 보고 나는 스피드 멱과 관련이 있다고 내기를 걸었다. 코드 뒤에 세부 문제 해결 및 분석: 문제풀이: T의 범위를 보면 블로거...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.