Блог пользователя dush1729

Автор dush1729, история, 9 лет назад, По-английски

I want to know how can i compare two different outputs so that i can check whether an algorithm works fine for corner cases also. I want to compare output generated by naive algorithm and an another algorithm saved in two .txt files. I use Code Blocks.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор dush1729, история, 9 лет назад, По-английски

I tried to solve FACTMUL and got AC with 4.82 time. There are many submissions with less than 1.0 time. How to do it in less than 1.0 time?

My code

#include<bits/stdc++.h>
unsigned long long mod=109546051211,fact[587117]={0,1,2,6},a[587117]={0,1,2,12},i,j;
unsigned long long mulmod(unsigned long long a,unsigned long long b)
{
    if((a==0)||(b<mod/a)) return (a*b)%mod;
    unsigned long long x=0,y=a%mod;
    while(b>0)
    {
        if(b%2==1) x=(x+y)%mod;
        y=(y*2)%mod;
        b/=2;
    }
    return x%mod;
}
int main()
{
    for(j=2;j<587117;j++)  //Computes and stores factorial
    {                      //of all number till 587116
        if(fact[j]) continue;
        fact[j]=mulmod(j,fact[j-1]);
    }
    unsigned long long n;
    scanf("%llu",&n);
    if(n>=587117) printf("0\n");
    else
    {
        if(a[n]!=0) printf("%llu\n",a[n]); //It will make no difference
        else                               //because test case is 1
        {
            for(i=2;i<=n;i++) a[i]=mulmod(fact[i],a[i-1]);
            printf("%llu\n",a[n]);
        }
    }
    return 0;
}

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор dush1729, 9 лет назад, По-английски
Let a = ( 2 ^ 9 ) * ( 3 ^ 2 ) * ( 7 ^ 1 ) * ( 11 ^ 1 )
and b = ( 2 ^ 2 ) * ( 3 ^ 4 ) * ( 7 ^ 1 ) * ( 13 ^ 2 )

then our answer will be ( 2 ^ 9 ) * ( 11 ^ 1 )

I can easily which factors will be present in the answer by calculating a / gcd(a,b) but i am having difficulty in finding the power of those factors. Is it possible to solve the problem using gcd and lcm? Or we will have to factorize both a and b then find the answer?

EDIT — Or is it possible to just find the factors having the exact same power? For above example it is ( 7 ^ 1 ).

For a = ( 2 ^ 3 ) * ( 3 ^ 2 ) * ( 5 ^ 3 ) * ( 7 ^ 1 )
and b = ( 2 ^ 4 ) * ( 3 ^ 2 ) * ( 7 ^ 1 ) * ( 17 ^ 2 )
it is ( 3 ^ 2 ) * ( 7 ^ 1 )

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор dush1729, история, 9 лет назад, По-английски

Hi i am trying to solve above problem and getting WA. Help.

#include<stdio.h>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        char a[1000];
        int i,b=0,c=0,d=0;
        fflush(stdin);
        gets(a);
        fflush(stdin);
        gets(a);
        for(i=0;a[i]!=' ';i++)
        {
            if(a[i]=='m')
            {
                b=-1;
                break;
            }
            b=b*10+(a[i]-'0');
        }
        for(;a[i]!=' ';i++);
        i+=3;
        for(;a[i]!=' ';i++)
        {
            if(a[i]=='m')
            {
                c=-1;
                break;
            }
            c=c*10+(a[i]-'0');
        }
        for(;a[i]!=' ';i++);
        i+=3;
        for(;a[i]!='\0';i++)
        {
            if(a[i]=='m')
            {
                d=-1;
                break;
            }
            d=d*10+(a[i]-'0');
        }
        if(b==-1) printf("%d + %d = %d\n",d-c,c,d);
        else if(c==-1) printf("%d + %d = %d\n",b,d-b,d);
        else printf("%d + %d = %d\n",b,c,b+c);
    }
    return 0;
}

PS — I got AC. I was getting WA because there were many blank lines in input.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится