Google Code Jam Japan 2011 #3

例の解けないB問題のlarge、集合同士の合併は無いと思っていたのですが計算してみたらどうやらあるらしい。そこで忠実に集合の合併を行うようにコードを修正してみました。とりあえず答えは正しいのですが、どういうときに集合の合併が起きるのかいまだによくわからないです。

------------------------------
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER) && _MSC_VER<1300
#define longlong _int64
#define PLLD "%I64d"
#else
#define longlong long long
#define PLLD "%lld"
#endif

#define PLD "%ld"
#define PD "%d"


int p[1000001];
int rank[1000001];
char isPrime[1000001];

int root(int x) {
    if (p[x] != x)
        p[x] = root(p[x]);
    return p[x];
}
  
void funion(int a, int b) {
    int aa,bb;
    aa=a,bb=b;

    a = root(a);
    b = root(b);
    //printf("SS a=%d b=%d root(a)=%d root(b)=%d rank[a]=%d ranl[b]=%d\n",aa,bb,a,b,rank[a],rank[b]);

    if (rank[a] < rank[b]){
        p[a] = b;
    }
    else {
        p[b] = a;
        if (rank[a] == rank[b]){
            rank[a]++;
            //if(rank[a]>=2){
            //    printf("kita!\n");
            //}
        }
    }
    //printf("EE a=%d b=%d root(a)=%d root(b)=%d rank[a]=%d ranl[b]=%d\n",aa,bb,a,b,rank[a],rank[b]);
}
  
int main(){
    FILE *fi=NULL,*fo=NULL;
    char buf[1024];

    int i,j,y;
    int caseCnt,caseNum;

    //fi=fopen("test.txt","rt");
    //fi=fopen("B-small-practice.in","rt");
    fi=fopen("B-large-practice.in","rt");

    //fo=fopen("result.txt","wt");
    //fo=fopen("result-small.txt","wt");
    fo=fopen("result-large.txt","wt");

    if(fi==NULL || fo==NULL)goto end;


    fgets(buf,sizeof(buf),fi);
    sscanf(buf,PD,&caseCnt);

  
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0]=0;
    isPrime[1]=0;
    for (i=2; i<=1000000; i++)
        for (j=2*i; j<=1000000; j+=i)
            isPrime[j] = 0;


    for (caseNum=1; caseNum <= caseCnt; caseNum++) {
            longlong A,B;
            longlong x;
            int P;
            int res;

            fgets(buf,sizeof(buf),fi);
            sscanf(buf,PLLD PLLD PD ,&A,&B,&P);

            for (i=0; i < B - A + 1; i++) {
                p[i] = i;
                rank[i] = 0;
            }
            res = (int)(B - A + 1);
            for (i=P; i<=1000000; i++) {
                if (!isPrime[i]) continue;
                x = A / i * i;
                if (x < A) x += i;
                x -= A;
                for (y=(int)x+i; y < B - A + 1; y += i)
                    if (root((int)x) != root(y)) {
                        res--;
                        funion((int)x, y);
                    }
            }
            printf("Case #" PD ": " PD "\n",caseNum,res);
            fprintf(fo,"Case #" PD ": " PD "\n",caseNum,res);
            //break;
        }

end:
    if(fi)fclose(fi);
    if(fo)fclose(fo);
    return 1;



------------------------------