BigMod and BigsumMod

/* Bismillahir Rahmanir Rahim BigMod of Series: (1 + b + b^2 + b^3 + b^4 +......+ b^(p-1) )%mod */ #include<bits/stdc++.h> #define ll long long using namespace std; ll b, p, m; ll bigmod(ll b, ll p, ll m){ // its the BigMod if(p==0) return 1; ll x=bigmod(b, p/2, m); x=(x*x)%m; if(p%2==1) x=(x*b)%m; return x; } ll bigsummod(ll b, ll p, ll m){ // mod in every line if(p==2) return (1+b)%m; // when 2 term (1+b) else if(p==3) return (1+b+b*b)%m; else if(p%2==1) return (1+b*bigsummod(b, p-1, m))%m; else{ ll xx=bigsummod(b, p/2, m)%m; return xx=(xx+(bigmod(b, p/2, m)*xx))%m; } } int main(){ while(cin>>b>>p>>m){ // b=Base, p=power+1(number of term), m=mod cout<<bigsummod(b, p, m)<<endl; } return 0; }

Factorial এর Digit সংখ্যা

যদি 100!(বা এর চেয়ে বড়) এর digit সংখ্যা বের করতে বলে সেক্ষেত্রে 100! এর মান বের করে digit count করব ?না, খুব মজার উপায় আছে। এই ক্ষেত্রে আমাদের সাহায্য করবে log, অনেক মজার একটা জিনিস, যত একে চিনছি ততই মজা পাচ্ছি। calculator এ log(10)=1,  log(100)=2,  log(105)=2.021189299,  log(1000)=3 । ঘটনা কি ঘটছে এতক্ষণে বুঝে ফেলার কথা । 100 এর digit সংখ্যা = log(100)+1 = 3. এটাতো একটা সংখ্যার জন্য পেলাম কিন্তু আমাদের লাগবে 100! এর জন্য। log এর ছোটবেলার সূত্র ভুলে গেলে চলবে না  log(a*b)=log(a)+log(b).
100! = 100*99*98*97*.......................*2*1
100! এর digit সংখ্যা = log(100)+log(99)+................+log(2)+log(1).
এই কাজ calculator এ মান ঠিক এই রকম আসলেও code এর compiler এ কিন্ত ঠিক এমন আসে না । এর কারণ হল calculator এ log এর মানটা আসলে 10 ভিত্তিক log এর মান। আর আমাদের সাধারণ Number System হল 10 ভিত্তিক । compiler এ log এর যে মান আসছে সেই মানকে log(10) দ্বারা ভাগ করলে  10 ভিত্তিক 

Solution of Light OJ 1109 - False Ordering

/* Bismillahir Rahmanir Rahim Saving number of divisor for every number and sorting using structure. */ #include<bits/stdc++.h> using namespace std; int t, n, i, j, cs=1; struct all{ int num; int ds; }one[1001]; bool comp(all f, all s){ // sort of structure if(f.ds==s.ds) return f.num>s.num; else return f.ds<s.ds; } void cal(){ // main calculation for all numbers for(i=1; i<=1000; i++){ one[i].num=i; one[i].ds=1; } for(i=1; i<=500; i++){ for(j=2*i; j<=1000; j+=i){ one[j].ds=one[j].ds+1; } } } int main(){ cal(); sort(one, one+1001, comp); cin>>t; while(t--){ cin>>n; cout<<"Case "<<cs++<<": "<<one[n].num<<endl; } return 0; }

Segmented Sieve-All Primes in Range

/* Bismillahir Rahmanir Rahim Segmented Sieve-Prime number in big range (10^14). Given two number (10^14) and given all primes in range. First execute all the primes bellow sqrt(b). */ #include<bits/stdc++.h> #define ll long long using namespace std; ll t, a, b, p, st, i, j, k; bool prime[10000007], ar[1000006]; void primes(ll x){ // mind, 2 is prime for(ll i=3; i*i<=x; i+=2){ if(prime[i]){ for(ll j=i*3; j<=x; j+=i*2) prime[j]=false; } } } int main(){ while(cin>>a>>b){ p=sqrt(b+1); for(i=0; i<=p; i++) prime[i]=true; for(i=0; i<=(b-a); i++) ar[i]=true; primes(p); for(i=3; i<=p; i+=2){// we don't execute the even number if(prime[i]){ st=a; if(st%i) st=a+(i-(st%i)); // use i not ar[i] if(st==i) st=st*2; //if the first number is prime for(k=st; k<=b; k+=i) ar[k-a]=false; } } if(a==2) cout<<2<<" "; // special case st=0; if(a%2==0) st=1; // its for skipping even number for(i=st; i<=(b-a); i+=2){ //we don't touch even number if(ar[i]) cout<<i+a<<" "; } cout<<endl; } return 0; } /* Input: 100000000000000 100000000100000 Output: (big output, to see run the code) */

Sieve-All Primes from 2 to n

/* Bismillahir Rahmanir Rahim Sieve-all primes from 1 to n */ #include<bits/stdc++.h> #define ll long long using namespace std; bool ar[10000009]; void sieve(ll x){ for(int i=3; i*i<=x; i+=2){ if(ar[i]){ for(int j=i*3; j<=x; j+=i*2) ar[j]=false; } } } int main(){ ll n, k; while(cin>>n){ memset(ar, true, sizeof(ar)); sieve(n); cout<<2<<" "; for(k=3; k<=n; k+=2){ if(ar[k])cout<<k<<" "; } cout<<endl; } return 0; }

Primality Checking

/* Bismillahir Rahmanir Rahim Time Complexity: O(sqrt(n)/2) */ #include<bits/stdc++.h> #define ll long long using namespace std; ll n, i; bool isPrime(int n){ if(n<2 || (n!=2 && n%2==0)) return false; else{ for(i=3; i*i<=n; i+=2){ if(n%i==0) return false; } } return true; } int main(){ while(cin>>n){ if(isPrime(n)) cout<<"Prime"<<endl; else cout<<"Not Prime"<<endl; } return 0; }

Solution of Light OJ 1099 - Not the Best

/* Bismillahir Rahmanir Rahim Solution-Using Dijkstra. Calculate shortest path and second shortest path for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define ll long long using namespace std; vector<ll>vt[5009], cost[5009]; ll n, en, d1[5009], d2[5009], sz; //d2[]=second shortest, d1[]=shortest struct node{ ll u, w; node(ll a, ll b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; q.push(node(st, 0)); fi(1, n){d1[i]=30000000, d2[i]=30000000;} d1[st]=0; while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; int uu=cost[u][i]; // mind it if(d1[u]+uu<d1[v]){ ll temp=d1[v]; d1[v]=d1[u]+uu; d2[v]=min(temp, min(d2[v], min(d2[u]+uu, d1[u]+3*uu))); q.push(node(v, d1[v]+d2[v])); } else if(d1[u]+uu<d2[v] && (d1[u]+uu)>d1[v]){ d2[v]=d1[u]+uu; } else{ d2[v]=min(d2[v], min(d2[u]+uu, d1[u]+3*uu)); } } } } int main(){ int t, cs=1, st, e, u, v, w, nn, ans; cin>>t; while(t--){ cin>>n>>e; fi(1, e){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } ll back=100000009; // Its for a special case, given bellow fi(0, vt[1].size()-1){ back=min(back, 2*cost[1][i]); } dijkstra(1); back=d1[n]+back; cout<<"Case "<<cs++<<": "<<min(back, d2[n])<<endl; fi(0, n){ vt[i].clear(); cost[i].clear(); } } return 0; } /* Special Case Input: 1 4 5 1 2 3 2 3 7 3 4 4 1 2 4 4 1 4 Output: Case 1: 10 */