Be a programmer,be logical

বুধবার, ১৩ এপ্রিল, ২০১৬

LightOJ 1098 - A New Function

Today we will discuss about a problem of LightOJ 1098 - A New Function:

At first the basic concept which will need that is for :

(A number $d$ appears $\lfloor N/d\rfloor$ times as a divisor of the numbers $1\ldots N$ . (Try it on paper if you don't see this) Because the number itself should not be counted, we have to substract 1 from this. This leads to this algorithm: $\sum _{{2\leq d\leq N}}d(\lfloor {\frac {N}{d}}\rfloor -1)$ . This formula gives the right results, but is way to slow. )

Let P = 1 - 25

let for 25 there is (25/2)-1 times two's in her and for 25 there are (25/3)-1 times

3's and like this,(25/4)-1 times 4's and (25/5)-1 times 5's,(25/6)-1 times 6's........

...(25/12)-1 times 12 and then it is not possible to go further.

now here comes the main process ,that is calculation...

here we make a list for 25:

There are 2: 11 times;

3: 7 times;

4:5 times;

5:4 times;

8: 2 times;

9=1 times;

10=1 times;

11:1 time;

....

12:1 times;

now we will calculate the sum for 1 to 12;

that is let i=12, the p=(i(i+1))/2-(12))/2(as,upto 1 was not present); still there remains (11-1) two's;

q=2*10;

then,we will calculate like this for 3 to 8;

then for 4 to 6 and at last 5 to 5;

by this we will get the result.

#include <bits/stdc++.h>
#include <math.h>
#define ll long long int
#define Max 1000
using namespace std;
ll y;
ll recursion(ll sum,ll a,ll k)
{ ll p,q;

    p=(k(k+1))/2-(((a-1)a)/2);
    q=a*(k-a);
   if(q>=0) sum=sum+(p+q);
    if(q<=0) return sum;
   else {
       a++;
   k=y/a;
   if(a>k) return sum;
        recursion(sum,a,k);
   }

}
int main(){
ll tc,cnt=1;
cin>>tc;
while(tc--){
    ll a,x,sum=0;
   scanf("%lld",&y);
    x=recursion(0,2,y/2);
   printf("Case %lld: %lld\n",cnt++,x);

}
}

you can also check: http://rizoantoufiq.blogspot.com/2015/12/lightoj-1098-new-function.html

শনিবার, ২ এপ্রিল, ২০১৬

Be a programmer,be logical : Goldbach's Conjecture(Number theory)

Be a programmer,be logical : Goldbach's Conjecture(Number theory):

Goldbach's Conjecture(Number theory)

Now i am going to discuss about an important theory of number theory that is Goldbach's conjecture.Hope u will enjoy:

For any integer n (n ≥ 4) there exist two prime numbers p₁ and p₂ such that p₁ + p₂ = n. In a problem we might need to find the number of essentially different pairs (p₁, p₂), satisfying the condition in the conjecture for a given even number n (4 ≤ n ≤ 2¹⁵). (The word ‘essentially’ means that for each pair (p₁, p₂) we have p₁≤ p₂.)For example, for n = 10 we have two such pairs: 10 = 5 + 5 and 10 = 3 + 7.

To solve this,as n ≤ 2¹⁵ = 32768, we’ll fill an array primes[32768] using function seive. We are interested in primes, not greater than 32768.

The function FindSol(n) finds the number of different pairs (p₁, p₂), for which n = p₁ + p₂. As p₁ ≤ p₂, we have p₁ ≤ n/2. So to solve the problem we need to find the number of pairs (i, n – i), such that i and n – i are prime numbers and 2 ≤ i ≤ n/2.

int FindSol(int n)

{

int i, res=0;

for(i=2;i<=n/2;i++)

if(flag[i] && flag[n-i])

res++;

return res;

}

******another effective******

For this all the primes should be generated first