### akash2504's blog

By akash2504, 7 years ago, ,

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

• +3

By akash2504, 8 years ago, ,

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;
}



• 0

By akash2504, 8 years ago, ,

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 total;
}T[MAX];

void update(LL Node,LL left,LL right,LL i,LL j,LL v){
if(i==left && j==right){
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;
else{
LL ret =0;
return ret;
}

}

int main(){
LL t;
scanf("%lld",&t);
while(t--){
scanf("%lld %lld",&n,&m);
for(LL i=0;i<=3*n;i++)
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

• +1

By akash2504, 8 years ago, ,

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

• 0

By akash2504, 8 years ago, ,

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

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;
}


• -4

By akash2504, 8 years ago, ,

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;
}


• -15

By akash2504, 8 years ago, ,

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

• 0

By akash2504, 8 years ago, ,

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