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

Solution of Light OJ 1067-Combinations

See the problem Light OJ 1067

#include<bits/stdc++.h> #define ll long long using namespace std; ll n, r, t, i, ans, cs=1, up, dwn, fac[1000009]; const ll mod=1000003; ll bigmod(ll b, ll p){ if(p==0) return 1; ll x=bigmod(b, p/2); x=(x*x)%mod; if(p%2==1)x=(x*b)%mod; return x; } int main(){ fac[0]=1; for(i=1; i<=1000000; i++){ fac[i]=(fac[i-1]*i)%mod; } cin>>t; while(t--){ cin>>n>>r; up=fac[n]; dwn=(fac[n-r]*fac[r])%mod; ans=up*bigmod(dwn, mod-2); cout<<"Case "<<cs++<<": "<<ans%mod<<endl; } return 0; }

Solution of Light OJ 1028 -Trailing Zeroes (I)

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll t, n, m, i, j, ans, prime[1000009], num[1000009]={0}, cnt, cs=1;

void seive(){
    for(i=3; i*i<=1000000; i+=2){
        if(num[i]==0){
            for(j=i*i; j<=1000000; j=j+(i*2)) num[j]=1;
        }
    }
    prime[0]=2;
    j=1;
    for(i=3; i<=1000000; i+=2){
        if(num[i]==0) prime[j++]=i;
    }
}

int main(){
    seive();
    scanf("%lld", &t);

    while(t--){
        cin>>n;
        ans=1;
        for(i=0; i<j&&prime[i]*prime[i]<=n; i++){
            cnt=0;
            while(n%prime[i]==0){
                cnt++;
                n=n/prime[i];
            }
            ans=ans*(cnt+1);
        }

        if(n!=1)ans=ans*2;
        cout<<"Case "<<cs++<<": "<<ans-1<<endl;

    }
    return 0;
}

Solution of UVa-11029 Leading and Trailing

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n, k, t_case;

ll bigmod(ll b, ll p, ll m){

    if(p==0)return 1;

    ll xx=bigmod(b, p/2, 1000);

    xx=(xx*xx)%1000;

    if(p%2==1)xx=(xx*b)%1000;

    return xx;
}

int main(){

    cin>>t_case;

    while(t_case){

        cin>>n>>k;

        /* executing first 3 digits */

        double x=k*(log10(n));

        x=x-(int)x; // taking fraction value only
        

        double ans=pow(10, x);

        ans=ans*100;

        cout<<(int)ans<<"...";

        /* executing last 3 digits */

        printf("%03d\n", bigmod(n, k, 1000));

        t_case--;

    }

    return 0;
}

Modular and Big Modular

মডুলার সম্পর্কে আমরা সবাই কম-বেশি জানি তবে মোটে না জানলেও সমস্যা নেই এটা খুব সহজ একটা বিষয় ।

modular

5%2=1

6%4=2

13%5=3

কিছু কি বোঝা যায় ? আসলে বিষয় হল, শেষ উদাহরণের জন্য বলি, 13 থেকে ছোট 5 এর সর্বচ্চ multiple হল 10 সুতরাং   13 mod 5 = (13-10) = 3. এখন তোমার (c/c++) compiler-এ 13%5 এবং -13%5 বের কর, দেখবে 3 এবং -3 উত্তর আসছে ।  প্রথম উত্তরটা ঠিক থাকলেও দ্বিতীয়টা ভুল, আসলে এখানে reminder বের করা হয়ছে ।

এখন দেখা যাক -13%5=? 

-13 এর থেকে ছোট 5 এর সর্বচ্চ multiple হল -15, সুতরাং -13%5 = (-13-(-15)) = -13+15 = 2 .

online judge এ মডুলো বের করার কোন সমস্যা সমাধানের সময় এই case টা মাথায় রাখা খুব জরুরী । তাহলে কিভাবে এই code টা করা যেতে পারে ? যে সংখ্যা দ্বারা mod করা হচ্ছে সেই সংখ্যার সাথে negative উত্তরটা যোগ করে দাও, হয়ে গেল ! না বুঝলে code টা দেখ, এটা negative, positive সব সংখ্যার জন্য ।

#include<bits/stdc++.h> using namespace std; int main() { long long m, n, r; while(cin>>m>>n){ r=m%n; if(r<0) r=r+n; cout<<r<<endl; } return 0; }

     100! %103=? এইটা পারবে ?

যদি 100! বের করে 103 দ্বারা মডুলো করতে চাও সেটা অসম্ভব । 100! এর কথা একটু চিন্তা করে দেখ ।

তবে আমরা জানি,       100!=(100*99*98*.......................3*2*1) 

দুইটা সুত্র দেখ 

                            1.  (a+b)%m = ((a%m)+(b%m))%m

                            2. (a*b)%m = ((a%m)*(b%m))%m

এখন দ্বিতীয় সুত্রটা ব্যবহার করে সমাধান করতে পারবে ।

আমাকে যদি বলে 12345678912345678912345678912 % 7 = ?

লক্ষ্য কর এখানে সংখ্যাটা 30 digit-এর । সাধারণত long long এ 19 digit পর্যান্ত নেয় unsigned long long নিলে সেখনে 20 digit পর্যান্ত calculate করবে । তাহলে কিভাবে 30-40 digit বা তার থেকে বেশি digit এর সংখ্যার মডুলো বের করতে পারি ?

 এখানে আমাদের string এর সাহায্য নিতে হবে কেননা string-এ 30-40 digit একটা মামুলি ব্যাপার। তবে এক্ষেত্রে দুইটা বিষয়ে ধারণা থাকতে হবে 

1.  321 = (((3*10)+2)*10)+1

            = ((30+2)*10)+1

            = (32*10)+1

            = 320+1

            =321

2. কোন digit এর character মান থেকে  integer মানে নিয়ে আসতে 48 বিয়োগ করতে হয় ।

এখন নিচের code-টা দেখ 

#include<bits/stdc++.h> using namespace std; int main() { int s=0, n, m, x, i; string a; cin>>a; cin>>m; n=a.size(); for(i=0; i<n; i++){ x=a[i]-48; s=(s*10+x)%m; } cout<<s<<endl; return 0; }