akash2504's blog

By akash2504, 6 years ago, In English,

Can i search questions on codeforces with tags? like questions on dp,number theory etc?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

I m trying to this problem on spoj ->> http://www.spoj.com/problems/PON/
but getting tle again n again. I have implemented miller-rabin primality test
help me
here is my code EDIT : Got Ac by optimizing power function

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
LL power(LL a,LL b,LL n){
	if(b==0)
		return 1;
	if(b==1) return a%n;
		LL c=power(a,b/2,n);
		if(b%2==0)
			return (c*c)%n;
		else
			 return ( ((c*c)%n) *( a%n))%n;
}
		
bool miller_test(LL n,LL k=1){
	if(n<2) return false;
	if(n==2|| n==3)return true;
	if(n%2==0)return false;
		int s=n-1;
		while(!(s&1)) s = s>>1;
		for(LL i=0;i<k;i++){
			LL flag=0;
			LL a = rand()%(n-3)+2;	
			LL x = power(a,s,n);
			if(x==1 || x==n-1)continue;
			while(s!=n-1 && x!=1 && x!=n-1){
				x = (x*x)%n;
				s=s<<1;
			}
			if(x!=n-1 && !(s&1))return false;
		}
		return true;
}

int main(){
int t;
scanf("%d",&t);
while(t--){
LL a;
scanf("%lld",&a);
	if(miller_test(a))printf("YES\n");
	else
		printf("NO\n");
}
return  0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

hello all .. i m trying to the problem http://www.spoj.com/problems/HORRIBLE/ but getting wa again n again... i have used segment trees with lazy propgation .. i have also solved similar problem http://www.spoj.com/problems/LITE/ but i couldnt understand y m gettin wa in this

here is my code....

#include<cstdio>
#define MAX 300000
typedef long long LL;
LL n,m;
struct tree{
LL add;
LL total;
}T[MAX];

void update(LL Node,LL left,LL right,LL i,LL j,LL v){
	if(i==left && j==right){
		T[Node].add += v;
		T[Node].total += (j-i+1)*v;
		return;
	}
	LL mid=(left + right)>>1, L = Node<<1 , R = L+1;
	if(j<=mid)update(L,left,mid,i,j,v);
	else if(i>mid)update(R,mid+1,right,i,j,v);
	else{
		update(L,left,mid,i,mid,v);
		update(R,mid+1,right,mid+1,j,v);
	}
	T[Node].total = T[L].total + T[R].total + T[Node].add*(right-left+1);
	
}
LL query(LL Node,LL left,LL right,LL i,LL j,LL v){
	if(i==left && j==right)return T[Node].total + v*(j-i+1);
	LL mid=(left + right)>>1, L = Node <<1 , R = L+1;
	if(j<=mid) return query(L,left,mid,i,j,v+T[Node].add);
	else if(i>mid)return query(R,mid+1,right,i,j,v+T[Node].add);
	else{
		LL ret =0;
		ret+= query(L,left,mid,i,mid,v+T[Node].add);
		ret+= query(R,mid+1,right,mid+1,j,v+T[Node].add);
		return ret;
	}
	
}

int main(){
LL t;
scanf("%lld",&t);
while(t--){
scanf("%lld %lld",&n,&m);
	for(LL i=0;i<=3*n;i++)
		T[i].total = T[i].add = 0;
while(m--){
	LL q,a,b,k;
	scanf("%lld %lld %lld",&q,&a,&b);
		switch(q){
			case 0:scanf("%lld",&k);
				update(1,0,n-1,a-1,b-1,k);break;
			case 1:printf("%lld\n",query(1,0,n-1,a-1,b-1,0));break;
		}
}
}
return 0;
}

checked on these test cases :

2
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
4 3
0 1 4 1
1 2 2
1 1

o/p

80
508
1
3

as provided in question :P

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

http://www.spoj.com/problems/PT07X/ Can someone help me to solve above problem? i m stuck n couldnt find any way through :(

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

Hello, i m trying the problem ' http://www.spoj.com/problems/SEQAGAIN/ '
but i m getting wa again and again

can anyone help me please....
as u can see i have used matrix exponentiation...
my approach:
1- the power k forms a fibonacci series.
2 matrix computed is
[ k k ] [ 1 0 ]
rest all is self explanatory
here's my code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MOD 1000000007
typedef long long LL;
LL k,h;
LL M[2][2],A[2][2],temp[2][2];
void matrix(LL n){
LL i,j,k;
	while(n){
	if(n&1){
		memset(temp,0,sizeof temp);
		for(i=0;i<2;i++)for(j=0;j<2;j++)for(k=0;k<2;k++)
				temp[i][j]=(temp[i][j]  +  ((A[i][k]%MOD)* (M[k][j]%MOD))%MOD)%MOD;
		for(i=0;i<2;i++)for(j=0;j<2;j++) A[i][j]=temp[i][j]%MOD;

	}
		memset(temp,0,sizeof temp);
		for(i=0;i<2;i++)for(j=0;j<2;j++)for(k=0;k<2;k++)
				temp[i][j]=(temp[i][j]+((M[i][k]%MOD)*(M[k][j]%MOD))%MOD)%MOD;
		for(i=0;i<2;i++)for(j=0;j<2;j++) M[i][j]=temp[i][j]%MOD;
		n/=2;
	}
}

LL power(LL a,LL b){
	if(b==0)
		return 1;
	if(b==1)
		return a%MOD;
	if(b%2==0){
		LL u = power(a,b/2)%MOD;
		return ((u%MOD)*(u%MOD))%MOD;
	}
	else{
		LL u = power(a,b/2)%MOD;
		return ((((u%MOD)*(u%MOD))%MOD) * (a%MOD))%MOD;
	}
}
int main(){
LL t;
scanf("%lld",&t);
while(t--){
LL a,b,ans,bns;
scanf("%lld %lld %lld %lld",&a,&b,&h,&k);
M[0][0]=k;M[0][1]=k;M[1][0]=1;M[1][1]=0;
A[0][0]=1;A[0][1]=0;A[1][0]=0;A[1][1]=1;
temp[0][0]=0;temp[0][1]=0;temp[1][0]=0;temp[1][1]=0;
if(h==0){ans=1;bns=0;}
else if(h==1){ans=0;bns=1;}
else{
matrix(h-1);
ans=A[0][1];bns=A[0][0];
}
//printf("%lld %lld\n",ans,bns);
LL final = ((power(a,ans)%MOD) * (power(b,bns)%MOD))%MOD;
printf("%lld\n",final);
}
return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

http://www.spoj.pl/problems/MAIN12B/ i m trying this problem but getting wa i have tried for many test cases but still couldnt get through my approach is 1- generated primes upto 10^6 using sieve 2- for each prime i checked if it divides any of the given numbers (since numbers are small n<100) and replaced it by a[i]/p 3- i chacked if some of the numbers are left in the array(other then 1) since they are prime greater than 10^6

plz correct me if i m wrong somewhere.... :(

here is my code


#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 1000005 typedef long long LL; LL prime[MAX]; LL num[100000]; int main(){ LL l=0; LL i,j; for(i=0;i<MAX;i++) prime[i]=1; prime[0]=0; prime[1]=0; for(i=2;i*i<=MAX;i++){ if(prime[i]){ for(j=i*i;j<MAX;j+=i) prime[j]=0; } } for(i=2;i<MAX;i++) if(prime[i]) num[l++]=i; LL test; scanf("%lld",&test); LL o=1; while(o<=test){ LL a[105]; LL n; printf("Case #%lld: ",o); scanf("%lld",&n); for(i=0;i<n;i++) scanf("%lld",&a[i]); LL flag=1; LL gh[100000],f=0; for(i=0;i<l;i++){ LL k=num[i]; LL s=1; for(j=0;j<n;j++){ if(num[i]<a[j])flag=0; if(a[j]%k==0&&a[j]!=1){ if(s){ gh[f++]=k; s=0;} while(a[j]%k==0) a[j]/=k; } } if(flag==1)break; } for(i=0;i<n;i++) if(a[i]!=1&&a[i]>MAX) gh[f++]=a[i]; printf("%lld\n",f); for(i=0;i<f;i++) printf("%lld\n",gh[i]); o++; } return 0; }

Read more »

 
 
 
 
  • Vote: I like it
  • -15
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

can anyone suggest me how to solve http://www.spoj.pl/problems/ADV04B1

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By akash2504, 7 years ago, In English,

how to solve linear recurrences of the type... f(n) = (n-1) * f(n-1) + (2*n-1) * f(n-2) with matrix exponentiation?

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it