Euler’s Totient Function (or Euler Phi)- (light oj problem-1007)

#include<stdio.h>
#define max 5000009
unsigned long long phi[max];
int main()
 {
  unsigned   long long i,j;
   for(i=2;i<max;i++)
    {
        if(phi[i]==0)
            {
                phi[i]=i-1;
                for(j=i*2;j<max;j=j+i)
                    {
                        if(phi[j]==0)
                        {
                            phi[j]=j;

                        }
                        phi[j]=phi[j]-(phi[j]/i);
                    }
            }
    }
   unsigned   long long s,d=0;
     for(s=2;s<max;s++)
      {
         phi[s]= phi[s]*phi[s];
         phi[s]=phi[s]+phi[s-1];
      }
     unsigned long long a,b,x,test,u;
      scanf("%llu",&test);
       for(u=1;u<=test;u++){
        scanf("%llu %llu",&a,&b);
          printf("Case %llu: %llu\n",u,phi[b]-phi[a-1]);
      }
   }

How to find the number of digits in factorial of n of base b?

LightOJ 1045 – Digits of Factorial

Answer: 

1. At first Precalculate the logarithms of number 1 to n and add them all in an array, say, sum[n].
   sum[n]=log(1)+log(2)+....+log(n).
2. Now divide sum[n] by the log of b: log(b).
3. result= sum/log(b).
4. Add 1 to the result for final result.
5. Ans= result+1;
6. For any value of n you just need to divide sum[n] and you can get the result at O(1).

Solution:-

#include<bits/stdc++.h>

using namespace std;

long long i;

double dig[1000010];

main()

{

    long long n,cs=1;

    scanf("%lld",&n);

    for(i=1;i<=1000000;i++)

    {

        dig[i]=dig[i-1]+log(i);

    }

    while(n--)

    {

        long long  a,b,sum=0,res;

        long long ans;

        scanf("%lld%lld",&a,&b);

        res=(long long)(dig[a]/(dig[b]-dig[b-1]));

        ans=res+1;

        printf("Case %lld: %lld\n",cs++,ans);

    }

}

Find the minimum number of length n, such that it is simultaneously divisible by some numbers(2,3,5,7)

#include < bits / stdc++.h>

#include <iostream>

using namespace std;

main()

{

    long long n;

    while(cin>>n)

    {

        if(n==1||n==2)

            cout<<"-1"<<endl;

        else

        {

            if(n==3)

            {

                cout<<210<<endl;

            }

            else

            {

                string s;

                long long i,k,k1=0,l,k2,k3;

                s='1';

                for(i=0;i<n-1;i++)

                    {

                        s+='0';

                    }

                    l=s.size();

                for(i=0;i<l;i++)

                {

                    k=k1*10+(s[i]-48);

                    k1=k%210;

                }

                k2=210-k1;

                k3=l-1;

                char ch;

                while(k2!=0)

                {

                    ch=k2%10;

                    s[k3]=ch+48;

                    k2/=10;

                    k3--;

                }

                cout<<s<<endl;

            }

        }

    }

যেকোনো অংকের ক্ষুদ্রতম সংখ্যা যা ২,৩,৫,৭ দ্বারা বিভাজ্য- (just a technique)

যদি বলে ২,৩,৫,৭ দ্বারা বিভাজ্য হবে যেকোনো অংকের কোন ক্ষুদ্রতম সংখ্যা ও এমন কোন বৃহত্তম সংখ্যা আছে?

উদাহরনঃ ২,৩,৫,৭ দ্বারা বিভাজ্য ১ ও ২ অংকের ক্ষুদ্রতম সংখ্যা নাই

২,৩,৫,৭ দ্বারা বিভাজ্য ৩ অংকের ক্ষুদ্রতম সংখ্যা হবে ২১০

২,৩,৫,৭ দ্বারা বিভাজ্য ৪ অংকের ক্ষুদ্রতম সংখ্যা হবে ১০৫০

সমধান করার নিয়মঃ-

প্রথমে আমার বের করতে হবে ৪ অংকের সবচেয়ে ক্ষুদ্রতম সংখ্যা কি?

আমরা জানি ১০০০ এবং ৪ অংকের সবচেয়ে বৃহত্তম সংখ্যা ৯৯৯৯

এইবার বের করবো ২,৩,৫,৭ এর ল.সা.গু. কত? উত্তরঃ-২১০

ক্ষুদ্রতম সংখ্যা(১০০০) কে ২১০ দ্বারা ভাগ করলে ভাগশেষ কত থাকে? উত্তরঃ-১৬০

এইবার বের করবো এই ভাগশেষ লসাগু অপেক্ষা কত ছোট? উত্তরঃ-(২১০-১৬০)=৫০

এই সংখ্যা টাকেই ঐ ক্ষুদ্রতম সংখ্যার সাথে যোগ করলেই উত্তর পেয়ে যাবো

অতএব ১০০০+৫০=১০৫০ ই হল ৩ অংকের সেই ক্ষুদ্রতম সংখ্যা যা ২,৩,৫,৭ দ্বারা বিভাজ্য।

#ঠিক একইভাবে ৪ অংকের জন্যঃ-

১০০০০ হল ৫ অংকের ক্ষুদ্রতম সংখ্যা,ভাগশেষ =(১০০০০%২১০)=১৩০

লসাগু থেকে ভাগশেষ বিয়োগঃ-২১০-১৩০=৮০;

৪ অংকের ক্ষুদ্রতম সংখ্যা+(লসাগু-ভাগশেষ)=১০০০০+(২১০-১৩০)=১০০৮০

১০০০০+৮০=১০০৮০ এইটাই উত্তর

code link:-http://smollick.blogspot.com/2016/11/find-minimum-number-of-length-n-such_4.html