TopCoder SRM 596 Div 2第3題
Problem Statement
For an integer n, let F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2), where k is the largest integer such that n - k^2 > 0. You are given three long longslo, hi and divisor. It is guaranteed thatdivisor will be a prime number. Compute and return the number of integers n betweenlo and hi, inclusive, such that F(n) is divisible bydivisor.
Definition
Class:
SparseFactorialDiv2
Method:
getCount
Parameters:
long long, long long, long long
Returns:
long long
Method signature:
long long getCount(long long lo, long long hi, long long divisor)
(be sure your method is public)
Constraints
-
lo will be between 1 and 1,000,000,000,000, inclusive.
-
hi will be between lo and 1,000,000,000,000, inclusive.
-
divisor will be between 2 and 997, inclusive.
-
divisor will be a prime number.
Examples
0)
4
8
3
Returns: 3
The value of F(n) for each n = 4, 5, ..., 8 is as follows. F(4) = 4*3 = 12 F(5) = 5*4*1 = 20 F(6) = 6*5*2 = 60 F(7) = 7*6*3 = 126 F(8) = 8*7*4 = 224
Thus, F(4), F(6), F(7) are divisible by 3 but F(5) and F(8) are not.
1)
9
11
7
Returns: 1 F(9) = 9*8*5 = 360 F(10) = 10*9*6*1 = 540 F(11) = 11*10*7*2 = 1540
Only F(11) is divisible by 7.
2)
1
1000000000000
2
Returns: 999999999999
Watch out for the overflow.
3)
16
26
11
Returns: 4
4)
10000
20000
997
Returns: 1211
5)
123456789
987654321
71
Returns: 438184668
タイプ:数論難易度:2.5
題意:lo,hi,divの3つの数を与えて、関数を定義します
F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2)
kはn−k^2>0を満たす最大整数である.
[lo,hi]区間でF(n)がdivで割り切れる数を満たす個数を求める.
解析:[lo,hi]のすべての数を直接遍歴し、F(n)がdivによって除去されるかどうかを判定することは不可能であり、hi-loの数級は10^12であるべきである.
ここで素数を計算する考え方(小さい頃から素数を探して素数の整数倍を非素数と表記する)を考え、F(n)がdivで割り切れるとF(n)の因数(n-k^2)、0<=k<√nは必ず少なくとも1つdivで割り切れる、つまりn-y^2=div*xとなるのでdiv*x+y^2,x>=1,y>=0という式の値を考え、この式の値が[lo,hi]区間に落ちると、では、この数は要求を満たしています.では,x,yを遍歴し,区間内に落ちた値を1つの結果setセットに加えて重くないことを保証し,最後にsetの大きさを統計することが結果である.しかし複雑度は依然として高く,div=2の場合,複雑度は10^12*10^6であることを考慮すると,明らかに受け入れられない.必ず複雑さを10^6に下げます.
上記の方法を簡略化することを考慮すると、外層サイクルはxを遍歴し、区間内に落ちるdiv*x+y^2を探すので、[div*x,div*(x+1))区間ごとの合法的なnの個数を知ることができれば、xが区間内に落ちる可能性値を乗じてO(1)で結果を算出することができる.この考え方を用いて、さらに細かくし、境界条件に注意する.
rc[i]をy^2%div=iとすると、y^2/divの値にさらに1が加算され、この残数がdivの数番目の倍数に最初に現れることを示す.すべてのy,1<=y<√hiを遍歴し,rc配列の値を得た.
rc配列に現れる残数の数cnt,すなわちdiv個数当たりどれだけの条件を満たすかを再計算する.さらに、すべてのrc配列の最大値stを計算する.すなわち、divの数番目の倍数から、後続のdiv個数ごとにcnt個が要求を満たす数があるに違いない.
その後,lo,hiの2つの数の境界条件を考慮して,[lo,div*left]区間と[div*right,hi]区間内で要求を満たす数の個数を記録し,leftはdiv*left>=loを満たす最小値,rightはdiv*right<=hiを満たす最大値をとる.
そして、このときのleftとstの関係を考慮して、leftその後、[left,right]区間内の要求に合致する個数、すなわちcnt*(right-left)を計算することができる.
コードは次のとおりです.
For an integer n, let F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2), where k is the largest integer such that n - k^2 > 0. You are given three long longslo, hi and divisor. It is guaranteed thatdivisor will be a prime number. Compute and return the number of integers n betweenlo and hi, inclusive, such that F(n) is divisible bydivisor.
Definition
Class:
SparseFactorialDiv2
Method:
getCount
Parameters:
long long, long long, long long
Returns:
long long
Method signature:
long long getCount(long long lo, long long hi, long long divisor)
(be sure your method is public)
Constraints
-
lo will be between 1 and 1,000,000,000,000, inclusive.
-
hi will be between lo and 1,000,000,000,000, inclusive.
-
divisor will be between 2 and 997, inclusive.
-
divisor will be a prime number.
Examples
0)
4
8
3
Returns: 3
The value of F(n) for each n = 4, 5, ..., 8 is as follows.
Thus, F(4), F(6), F(7) are divisible by 3 but F(5) and F(8) are not.
1)
9
11
7
Returns: 1
Only F(11) is divisible by 7.
2)
1
1000000000000
2
Returns: 999999999999
Watch out for the overflow.
3)
16
26
11
Returns: 4
4)
10000
20000
997
Returns: 1211
5)
123456789
987654321
71
Returns: 438184668
タイプ:数論難易度:2.5
題意:lo,hi,divの3つの数を与えて、関数を定義します
F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2)
kはn−k^2>0を満たす最大整数である.
[lo,hi]区間でF(n)がdivで割り切れる数を満たす個数を求める.
解析:[lo,hi]のすべての数を直接遍歴し、F(n)がdivによって除去されるかどうかを判定することは不可能であり、hi-loの数級は10^12であるべきである.
ここで素数を計算する考え方(小さい頃から素数を探して素数の整数倍を非素数と表記する)を考え、F(n)がdivで割り切れるとF(n)の因数(n-k^2)、0<=k<√nは必ず少なくとも1つdivで割り切れる、つまりn-y^2=div*xとなるのでdiv*x+y^2,x>=1,y>=0という式の値を考え、この式の値が[lo,hi]区間に落ちると、では、この数は要求を満たしています.では,x,yを遍歴し,区間内に落ちた値を1つの結果setセットに加えて重くないことを保証し,最後にsetの大きさを統計することが結果である.しかし複雑度は依然として高く,div=2の場合,複雑度は10^12*10^6であることを考慮すると,明らかに受け入れられない.必ず複雑さを10^6に下げます.
上記の方法を簡略化することを考慮すると、外層サイクルはxを遍歴し、区間内に落ちるdiv*x+y^2を探すので、[div*x,div*(x+1))区間ごとの合法的なnの個数を知ることができれば、xが区間内に落ちる可能性値を乗じてO(1)で結果を算出することができる.この考え方を用いて、さらに細かくし、境界条件に注意する.
rc[i]をy^2%div=iとすると、y^2/divの値にさらに1が加算され、この残数がdivの数番目の倍数に最初に現れることを示す.すべてのy,1<=y<√hiを遍歴し,rc配列の値を得た.
rc配列に現れる残数の数cnt,すなわちdiv個数当たりどれだけの条件を満たすかを再計算する.さらに、すべてのrc配列の最大値stを計算する.すなわち、divの数番目の倍数から、後続のdiv個数ごとにcnt個が要求を満たす数があるに違いない.
その後,lo,hiの2つの数の境界条件を考慮して,[lo,div*left]区間と[div*right,hi]区間内で要求を満たす数の個数を記録し,leftはdiv*left>=loを満たす最小値,rightはdiv*right<=hiを満たす最大値をとる.
そして、このときのleftとstの関係を考慮して、left
コードは次のとおりです.
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
class SparseFactorialDiv2
{
public:
long long getCount(long long lo, long long hi, long long divisor)
{
long long rc[1000];
memset(rc,-1,sizeof(rc));
rc[0] = 1;
for(long long i=1; i*i<hi; i++)
{
long long a = (i*i)/divisor;
long long b = (i*i)%divisor;
if(rc[b]<0) rc[b] = a+1;
}
long long st = -1, cnt = 0;
for(long long i=0; i<divisor; i++)
{
if(rc[i]>-1) cnt++;
if(rc[i]>st) st = rc[i];
}
long long lefta = lo/divisor;
long long leftb = lo%divisor;
long long righta = hi/divisor;
long long rightb = hi%divisor;
long long ans = 0;
if(lefta==righta)
{
for(long long i=leftb; i<=rightb; i++)
if(rc[i]>0 && lefta >= rc[i]) ans++;
}
else
{
for(long long i=leftb; i<divisor; i++)
if(rc[i]>0 && lefta >= rc[i]) ans++;
lefta++;
for(; lefta < st && lefta < righta; lefta++)
{
for(long long i=0; i<divisor; i++)
if(rc[i]>0 && lefta >= rc[i]) ans++;
}
for(long long i=0; i<=rightb; i++)
if(rc[i]>0 && righta >= rc[i]) ans++;
ans += cnt*(righta-lefta);
}
return ans;
}
};
int main()
{
}