Euler এর Totient Function ( ϕ )

                   Euler এর Totient Function ( ϕ )

প্রোগ্রামিং এ Totient Function একটা গুরুত্বপূর্ণ টপিক্স এবং অনেক মজারও।

প্রথমে জেনে নেই Totient Function টা কি...?

 Φ(n)=n এর সমান বা n থেকে ছোট এমন কতগুলো সংখ্যা যা n এর coprime.

Coprime এর অর্থ হল যাদের কোন সাধারণ গুণনীয়ক নেই।

যেমনঃ ১, ২ , ৩, ৪, ৫, ৬, ৭, ৮, ৯, ১০, ১১, ১২, ১৩, ১৪, ১৫, সংখ্যা গুলোর মধ্যে ১৫ এর সাথে (৩, ৫, ৬, ৯, ১০, ১২, ১৫) সংখ্যা গুলোর কোন না কোন সাধারণ গুণনীয়ক আছে। কিন্তু

বাকি (১,২,৪,৭,৮,১১,১৩,১৪) এই ৮ টি সংখ্যা গুলোর সাথে ১৫ এর কোন সাধারণ গুণনীয়ক নেই।সুতরাং Φ (১৫ )= ৮;

Φ(n)=n(1-1/p1)(1-1/p2)......(1-1/pk)

15 এর ক্ষেত্রে এর গুণনীয়ক   

                                   = ৩,৫ ;p1=3,p2=5;

১ম ক্ষেত্রেঃ

n(1-1/p1)=(n-n/ ৩)=( ১৫  -  ১৫/ ৩)…. এখানে  ১৫/৩ =৫ ,মানে হচ্ছে ১৫ এর ভিতর ৩ এর ৫ টি গুনিতক আছে, এবং (১৫-৫)=১০ টি সংখ্যা যাতে ৩ এর গুনতক নেই...প্রথমে এভাবে ৩ এর গুনতক বাদ দিলে থাকে ১০ টি সংখ্যা-(১,২,৪,৫,৭,৮,১০,১১,১৩,১৪)

n(1-1/p1)=১০;

২য় ক্ষেত্রেঃ

১০(1-1/p২)=(১০ - ১০ / ৫)…. এখানে  ১০/৫ =২ ,মানে হচ্ছে ১০ এর ভিতর ৫ এর ২ টি গুনিতক আছে, এবং (১০-২)=৮ টি সংখ্যা যাতে ৫ এর গুনতক নেই.. এভাবে ৫ এর গুনতক বাদ দিলে থাকে ৮ টি সংখ্যা-(১,২,৪,৭,৮,১১,১৩,১৪)

(১০-১০/৫)=৮;

সুতরাং Φ(১৫)=  ৮; এভাবে কোন একটা সংখার গুণনীয়ক গুলো বের করে আমরা সহজেই coprime বের করতে পারি। সহজে বলা যায় কোন একটা সংখ্যা ,যেমনঃ ১৫, এর সাথে ১৫ এর ছোট ঐ সংখ্যা গুলি যাদের সাথে ১৫ এর গ সা গু ১;ঐ সংখ্যা গুলি বের করার জন্য Totient Function  ব্যাবহার করা হয়।

                                        ’’ধন্যবাদ’’

light oj-1255

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char pat[1000009];
char txt[1000009];

int count;
void f_f(char *pat, int *f)
{
    f[0]=0;

    int len = 0,k=1;
   int p=strlen(pat);

     while (k < p)
     {
       if (pat[k] == pat[len])
        {
           len++;
           f[k]=len;
           k++;
        }
       else
       {
         if (len!=0) len = f[len-1];

         else
         {
             f[k]=0;
             k++;
         }
       }
    }
}

int KMPSearch(char *pat, char *txt)
{
    int p = strlen(pat);
    int t = strlen(txt);
int *f = (int *)malloc(sizeof(int)*p);

f_f(pat,f);

    int i  = 0,j=0;

     while (i < t)
    {
      if (pat[j] == txt[i])
      {
        j++;
        i++;
      }

      if (j == p)
      {
          count++;
           j = f[j-1];
         }

      else if (pat[j] != txt[i])
     {
        if (j!=0)
            j= f[j-1];

        else
            i++;

        }
}
free(f);

}
int main()
{
    int test,z=0,c;


    scanf("%d",&test);
     for(z=1;z<=test;z++){


      scanf("%s %s",txt,pat);
      count=0;
      KMPSearch(pat, txt);

    printf("Case %d: %d\n",z,count);}

    }

light oj 1007....Mathematically Hard

 #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]);
      }
   }

Solution Hints for Light oj 1008...

প্রথমে আমরা কিছু অংশে ভাগ করি।

১-৪ পর্যন্ত, ৫-৯ পর্যন্ত, ১০-১৬...

১-৪ এর ক্ষেত্রে...

৪ এর বর্গমূল মান=২ ।  বাকি ১,২,৩ কে বর্গমূল করে ceiling করলে মান হয় ২ ।

৫-৯ এর ক্ষেত্রে...

৯ এর বর্গমূল ৩ । বাকি  ৫,৬,৭,৮ কেও বর্গমূল করে ceiling করলে মান হয় ৩ ।

যদি চিত্রের নিচ থেকে row and column হিসেব করি...

এখানে একটা বিষয় লক্ষ্য করলে দেখা যাবে যে ৫-৯ থেকে আমরা ৩ পাই । এই ৩ হচ্ছে ৫-৯ এর row অথবা column মান ।

যেহেতু মান ৩ ,তাই ৯ থেকে ৩ টি সংখ্যা র জন্য row মান ৩...(৯,৮,৭)। ৬ ও ৫ এর ক্ষেত্রে কলাম এর মান ৩ হবে ।

এটা বের করার জন্য ( n*n-s<n) এই সূত্র ব্যবহার করা হয়েছে ।এই ক্ষেত্রে এটা সত্য হবে কেবলমাত্র ৯,৮,৭ এর জন্য এবং ৯,৮,৭ এর    হবে ৩ । এর কলাম এর ক্ষেত্রে দেখতে পাচ্ছি যে ৯ আছে ১ নং কলাম এ ,৮ আছে ২ নং কলাম এ, ৭আছে ৩ নং কলাম এ...

আমরা যদি ৯-৯=০ , ০+১=১...যা ৯ এর কলাম।। আবার ৯-৮=১ , ১+১=২..   যা ৮ এর কলাম।। আবার ৯-৮=১ , ১+১=২.. যা ৮ এর কলাম।।

আশা করি আপনি মোটামুটি বুঝতে পেরেছেন । ধন্যবাদ।

C solution for light oj 1006...

#include<stdio.h>
int main() {
long long int n,i,t,test=1, cases;
scanf("%lld",&t);
long long int ara[100000];
while( t--) {

for(i=0;i<=5;i++){
scanf("%lld",&ara[i]);}
scanf("%lld",&n);
for(i=6;i<=n;i++){
    ara[i]=(ara[i-1]+ara[i-2]+ara[i-3]+ara[i-4]+ara[i-5]+ara[i-6])%10000007;
}
printf("Case %lld: %lld\n",test++, ara[n]% 10000007);
}
return 0;
}