Dear fellow coders,
Following the frustration of failling to solve the third problem in round 1C
due to a lack of efficiency in the implementation of my algorithm, I looked
at other people's submission to get a grasp of how the did it. And here I
fail to understand their algorithm. Can you tell me what this part of code
does at the beginning of Burunduk's submission ? (Also, he uses a function
named __gcd, I think I know what it does with me being a very very smart guy
but my compiler won't find it, do you know where it is defined ?)
// a bunch of includes
using namespace std;
#ifdef _WIN32
# define I64 "%I64d"
#else
# define I64 "%Ld"
#endif
#define EOL(i, n) " \n"[i == (n) - 1]
#define LEN(a) (int)(sizeof(a) / sizeof(a[0]))
#define IS(a, i) (((a) >> (i)) & 1)
const int maxN = (int)1e4 + 10;
const ll inf = (ll)1e18;
const int maxX = (int)1e8 + 100;
const int maxP = (int)6e6;
unsigned char is[maxX / 8 + 1];
int pn = 0, p[maxP];
int N;
ll L, H, a[maxN], g[maxN], lcm[maxN];
int xn;
ll x[99];
int k[99];
vector <ll> D;
void go( ll val, int i )
{
if (i == xn)
{
D.pb(val);
return;
}
for (int j = 0; j <= k[i]; j++)
go(val, i + 1), val *= x[i];
}
void getD( ll X )
{
D.clear();
xn = 0;
for (int i = 0; i < pn && (ll)p[i] * p[i] <= X; i++)
if (X % p[i] == 0)
{
k[xn] = 0, x[xn] = p[i];
while (X % p[i] == 0)
k[xn]++, X /= p[i];
xn++;
}
if (X > 1)
k[xn] = 1, x[xn++] = X;
go(1, 0);
}
int main()
{
for (int i = 2; i * i < maxX; i++)
if (!IS(is[i >> 3], i & 7))
for (int j = i * i; j < maxX; j += i)
is[j >> 3] |= 1 << (j & 7);
for (int i = 2; i < maxX; i++)
if (!IS(is[i >> 3], i & 7))
p[pn++] = i;
What is in p[] at that point, and why/how ?
Cheers,
Ernest.
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
