Hi, this initial main part is just a very efficient implementation of the Sieve of Eratosthenes <http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>.
Instead of using 8 bits (boolean or char) to indicate if a number is marked or not it uses only 1 bit, and the shifting and and operators are to extract those bits. This information is inside the array is[] After this it puts in array p all primes. so p[k] is the kth prime. 2011/5/23 Ernest Galbrun <[email protected]> > 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. > -- 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.
