結果

問題 No.990 N×Mマス計算（Kの倍数）
コンテスト
ユーザー tails
提出日時 2021-06-29 18:05:50
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 3,264 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 35,840 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-25 20:16:05
合計ジャッジ時間 2,613 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:104:1: warning: return type defaults to 'int' [-Wimplicit-int]
  104 | main(){
      | ^~~~
main.c: In function 'main':
main.c:205:9: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration]
  205 |         write(1,wp,wbuf+sizeof wbuf-wp);
      |         ^~~~~
main.c:206:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration]
  206 |         _exit(0);
      |         ^~~~~
      |         _Exit

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

char*mmap();
#define rd(v) long v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}
#define wt(v) {long _z=v;do*--wp=_z%10+48;while(_z/=10);}
#define rep(v,e) for(long v=0;v<e;++v)

#define SIEVE_N 32000
int nprimes;
int primes[SIEVE_N];
char sieve[SIEVE_N];

void mkprimes(){
	primes[nprimes++]=2;
	for(int i=3;i<SIEVE_N;i+=2){
		if(sieve[i]==0){
			primes[nprimes++]=i;
			for(int j=i*i;j<SIEVE_N;j+=i*2){
				sieve[j]=1;
			}
		}
	}
}

int divisors(int a,int*divs){
	int n=0;
	divs[n++]=1;
	int i=0;
	int p;
	while(p=primes[i],a>=p*p){
		if(a%p==0){
			int k=1;
			while(a/=p,a%p==0){
				++k;
			}
			int n0=n*k;
			for(int j=0;j<n0;++j){
				divs[n++]=divs[j]*p;
			}
		}
		++i;
	}
	if(a>1){
		int n0=n;
		for(int j=0;j<n0;++j){
			divs[n++]=divs[j]*a;
		}
	}
	return n;
}

void radix_sort_aux(unsigned*a,unsigned*b,int n){
	int c[256];
	for(int i=0;i<256;++i){
		c[i]=0;
	}
	for(int i=0;i<n;++i){
		++c[a[i]&255];
	}
	int t=0;
	for(int i=0;i<256;++i){
		int u=c[i];
		c[i]=t;
		t+=u;
	}
	for(int i=0;i<n;++i){
		b[c[a[i]&255]++]=a[i]>>8|a[i]<<24;
	}
}

int rsbuf[100000];
void radix_sort(unsigned*a,int n){
	radix_sort_aux(a,rsbuf,n);
	radix_sort_aux(rsbuf,a,n);
	radix_sort_aux(a,rsbuf,n);
	radix_sort_aux(rsbuf,a,n);
}

long gcd(long a,long b){
	if(a==0||b==0){
		return a+b;
	}
	long x=__builtin_ctzl(a);
	long y=__builtin_ctzl(b);
	a>>=x;
	b>>=y;
	long c;
	while(c=a-b){
		c>>=__builtin_ctzl(c);
		if(c<0){
			b=-c;
		}else{
			a=c;
		}
	}
	return a<<(x<=y?x:y);
}

int sa[100000],sb[100000];
int kdivs[1500];
int ha[1500],hb[1500];

main(){
	char*rp=mmap(0l,1l<<25,1,2,0,0ll);
	rd(n);
	rd(m);
	rd(k);
	int op=*rp;
	rp+=2;
	long ans=0;
	if(op=='+'){
		rep(i,m){
			rd(bi);
			sb[i]=bi%k;
		}
		radix_sort(sb,m);
		rep(i,n){
			rd(ai);
			ai=(k-ai)%k;
			sa[i]=ai+(ai<0?k:0);
		}
		radix_sort(sa,n);
		long i=0,j=0;
		while(i<n&&j<m){
			if(sa[i]<sb[j]){
				++i;
			}else if(sa[i]>sb[j]){
				++j;
			}else{
				int v=sa[i];
				long di=0,dj=0;
				while(i<n&&sa[i]==v) ++i,++di;
				while(j<m&&sb[j]==v) ++j,++dj;
				ans+=di*dj;
			}
		}
	}else{
		mkprimes();
		long kdivn=divisors(k,kdivs);
		radix_sort(kdivs,kdivn);
		rep(i,m){
			rd(b);
			b=gcd(k,b);
			long lo=0,hi=kdivn;
			while(lo<hi-1){
				long mid=lo+hi>>1;
				if(b<kdivs[mid]){
					hi=mid;
				}else{
					lo=mid;
				}
			}
			hb[lo]+=1;
		}
		rep(i,n){
			rd(a);
			a=gcd(k,a);
			long lo=0,hi=kdivn;
			while(lo<hi-1){
				long mid=lo+hi>>1;
				if(a<kdivs[mid]){
					hi=mid;
				}else{
					lo=mid;
				}
			}
			ha[lo]+=1;
		}
		long keb=__builtin_ctzl(k);
		k>>=keb;
		unsigned long ket=~0ul/k;
		unsigned long ked=k;
		ked*=2-k*ked;
		ked*=2-k*ked;
		ked*=2-k*ked;
		ked*=2-k*ked;
		ked*=2-k*ked;
		rep(i,kdivn){
			{
				long x=(long)kdivs[i]*(long)kdivs[i];
				long xb=__builtin_ctzl(x);
				if(xb>=keb){
					x>>=xb;
					if(x*ked<=ket){
						ans+=(long)ha[i]*(long)hb[i];
					}
				}
			}
			rep(j,i){
				long x=(long)kdivs[i]*(long)kdivs[j];
				long xb=__builtin_ctzl(x);
				if(xb>=keb){
					x>>=xb;
					if(x*ked<=ket){
						ans+=(long)ha[i]*(long)hb[j];
						ans+=(long)ha[j]*(long)hb[i];
					}
				}
			}
		}
	}
	char wbuf[64],*wp=wbuf+sizeof wbuf;
	wt(ans);
	write(1,wp,wbuf+sizeof wbuf-wp);
	_exit(0);
}
0