WPC5I-LCM

LCM

given below c code for wpc5i spoj or lcm spoj.

If you have any problem you can ask me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,m;
  scanf("%d%d",&n,&m);
  map<int ,int>mp1,mp2,result;
  map<int ,int>::iterator t;
  for(int i=2;i*i<=n;i++)
  {
       while(n%i==0)
       {
           mp1[i]+=1;
           n/=i;
        }
  }
  if(n>1)
     mp1[n]+=1;
  for(int i=2;i*i<=m;i++)
  {
        while(m%i==0)
        {
            mp2[i]+=1;
            m/=i;
        }
  }
  if(m>1)
     mp2[m]+=1;
  long long k=1;
  for(t=mp1.begin();t!=mp1.end();t++)
  {
       if(t->second > mp2[t->first])
           result[t->first]=t->second;
  } 
  for(t=mp2.begin();t!=mp2.end();t++)
  {
       if(t->second > mp1[t->first] && result[t->first] < t->second)
            result[t->first]=t->second;
  }
  for(t=result.begin();t!=result.end();t++)
       for(int i=0;i<t->second;i++)
            k*=(long long)(t->first);
  printf("%lld\n",k);
 }
 return 0;
}

INS14B-TRISQRS

TRISQRS

Given below code is for ins14b spoj or trisqrs spoj.

Here the area of largest triangle possible in a square is (N*N)/2;

So we have to count the total number of divisors of  (N*N)/2.

My algorithm is very time consuming if any one can suggest me more fast algorithm for finding total number of divisors of a number please comment or mail me @ :-> raj.nishant360@gmail.com .That will be very help full to me.

#include <bits/stdc++.h>
using namespace std;
int num[1000009]={0};
void pre()
{
 for(int i=2;i<=1000;i++)
 {
  if(!num[i])
  for(int j=i*i;j<=1000000;j+=i)
   if(!num[j])
    num[j]=i;
 }
}
int main()
{
 int t;
 pre();
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  if(n&1){
   printf("0\n");
   continue;}
  n*=n;
  n>>=1;
  cout<<n<<endl;
  map<int ,int >mp;
  map<int ,int >::iterator t;
  if(num[n]!= 0)
   while(n%num[n] == 0)
   {
    mp[num[n]]+=1;
    if(num[n] == 0)
     break;
    n/=num[n];
    if(num[n]==0)
     break;
   }
  mp[n]+=1;
  int result =1;
  for(t=mp.begin();t!=mp.end();t++)
   result *= (t->second + 1);
  printf("%d\n",result);
 }
 return 0;
}