Hacker Rank - Unfriendly Numbers

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static int unfriendlyNumbers(long[] a,long k) {
        LinkedList<Long> factors=new LinkedList<Long>();
        for(long i=2;i<=Math.sqrt(k);i++){
            if(k%i==0){
                factors.add(i);
                if(k/i !=i){
                    factors.add(k/i);
                }
            }
        }
        HashSet<Long> hs=new HashSet<Long>();
        for(int i=0;i<a.length;i++){
               hs.add(gcd(a[i], k));
        }
        factors.add(k);
        int counter=0;
        while(!factors.isEmpty()){
            long div=factors.remove();
            boolean flag=true;
            for(long key: hs){
                if(key%div==0){
                    flag=false;
                }
            }
            if(flag){
                counter++;
            }
        }
        return counter;
    }
   
    public static long gcd(long x,long y){
        if(y==0)
            return x;
        return gcd(y, x%y);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        long n=Long.parseLong(st.nextToken()),k=Long.parseLong(st.nextToken());
        st=new StringTokenizer(br.readLine());
        long[]arr=new long[st.countTokens()];
        for(int i=0;i<arr.length;i++){
            arr[i]=Long.parseLong(st.nextToken());
        }
        System.out.println(unfriendlyNumbers(arr, k));
    }
}

UVA - 12708 - GCD The Largest

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n=0;
    long x=0;
    scanf("%d",&n);
    while(n--){
        scanf("%ld",&x);
        if(x%2!=0){
            x--;
        }
        printf("%ld\n",x/2);
    }
    return 0;
}

UVA - 10341 - Solve It

//Root finding algorithm using newton method
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        String m="";
        while((m=br.readLine())!=null){
            if("#".equals(m.trim()))
                break;
            StringTokenizer st=new StringTokenizer(m);
            int p=Integer.parseInt(st.nextToken()),
                    q=Integer.parseInt(st.nextToken()),
                    r=Integer.parseInt(st.nextToken()),
                    s=Integer.parseInt(st.nextToken()),
                    t=Integer.parseInt(st.nextToken()),
                    u=Integer.parseInt(st.nextToken());
            if(function(0, p, q, r, s, t, u) *function(1, p, q, r, s, t, u)>0){
               sb.append("No solution\n");
            }else{
               sb.append(String.format("%.4f\n",netwonMethod(p, q, r, s, t, u)));
            }
        }
        System.out.print(sb);
    }
    static double function(double i,int p,int q,int r,
                            int s,int t,int u){
        return 1.0*p*Math.exp(-i)+1.0*q*Math.sin(i)
                        +1.0*r*Math.cos(i)+1.0*s*Math.tan(i)+t*i*i+u;
    }
  
    static double dfunction(double i,int p,int q,int r,
                            int s,int t,int u){
        return -1.0*p*Math.exp(-i)+1.0*q*Math.cos(i)
                        -1.0*r*Math.sin(i)+1.0*s/(Math.cos(i)*Math.cos(i))+2*t*i;
    }
  
    static double netwonMethod(int p,int q,int r,
                            int s,int t,int u){
        if(function(0, p, q, r, s, t, u) ==0)
            return 0;
        double ans=0.5;
        while (true){
            double newans = ans - function(ans, p, q, r, s, t, u)/dfunction(ans, p, q, r, s, t, u);
            if (Math.abs(newans-ans) < eps)
                return ans;
            ans=newans;
        }
    }
    static double eps=1E-7;
}

UVA - 12043 - Divisors

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        long[] sums = new long[100 * 1000 + 1], counters = new long[100 * 1000 + 1];
        for (int i = 1; i < 100 * 1000 + 1; i++) {
            Point p = factors(i);
            counters[i] = (int) p.getX();
            sums[i] = (int) p.getY();
        }
        int cases = Integer.parseInt(br.readLine().trim());
        for (int i = 0; i < cases; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int a = 0, b = 0, k = 0;
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            long sum = 0;
            long counter = 0;
            for (int j = a; j < b + 1; j++) {
                if (j % k == 0) {
                    counter += counters[j];
                    sum += sums[j];
                }
            }
            sb.append(counter).append(" ").append(sum).append("\n");
        }
        System.out.print(sb);
    }

    static Point factors(int x) {
        long sum = 0;
        long counter = 0;
        for (int i = 1; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                counter++;
                sum += i;
                if (x / i != i) {
                    sum += x / i;
                    counter++;
                }
            }
        }
        return new Point(counter, sum);
    }
}
class Point {
    private long x;
    private long y;

    public Point(long x, long y) {
        this.x = x;
        this.y = y;
    }

    public long getX() {
        return x;
    }

    public void setX(long x) {
        this.x = x;
    }

    public long getY() {
        return y;
    }

    public void setY(long y) {
        this.y = y;
    }
   
}

UVA - 160 - Factors and Factorials

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        String m="";
        int[][]arr=new int[101][100];
        for(int i=2;i<arr.length;i++){
            System.arraycopy(arr[i-1], 2, arr[i], 2, 100 - 2);
            LinkedList<Integer> list=primeFactors(i);
            while(!list.isEmpty()){
                int temp=list.remove();
                arr[i][temp]++;
            }
        }
        while(true){
            int x=Integer.parseInt(br.readLine());
            if(x==0){
                break;
            }
            String str=String.format("%3d! =", x);
            sb.append(str);
            int counter=0;
            boolean flag=false;
            for(int i=2;i<100;i++){
                if(arr[x][i]>0){
                    if(flag){
                       sb.append("      ");
                       flag=false;
                    }
                    str=String.format("%3d", arr[x][i]);
                    sb.append(str);
                    counter++;
                    if(counter%15==0){
                        sb.append("\n");
                        flag=true;
                    }
                }
            }
            if(!flag){
                sb.append("\n");
            }
        }
        System.out.print(sb);
    }
   
    static LinkedList<Integer> primeFactors(int x){
        LinkedList<Integer> list=new LinkedList<Integer>();
        if(x<0){
            list.add(-1);
        }
        int temp=Math.abs(x);
        boolean notprime=false,entered=false;
        while(temp>1 &&!notprime){
            entered=false;
            for(int i=2;i<Math.sqrt(temp)+1;i++){
                if(temp%i==0){
                    list.add(i);
                    temp/=i;
                    notprime=false;
                    entered=true;
                    break;
                }
            }
            if(!entered)
                 notprime=true;
        }
        if(notprime){
                list.add(temp);
            }
        return list;
    }
}

UVA - 10489 - Boxes of Chocolates

#include<stdio.h>

int main()
{

   long n,friends,boxes,k,product,sum,temp;
   scanf("%ld",&n);
   while(n--){
      scanf("%ld %ld",&friends,&boxes);
      sum=0;
      while(boxes--){
         product=1;
         scanf("%ld",&k);
         while(k--){
            scanf("%ld",&temp);
            product=(product*temp)%friends;
         }
         sum=(sum+product)%friends;
      }
      printf("%ld\n",sum);
   }
   return 0;
}

UVA - 10515 - Powers Et Al.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        int[]mods={1, 1, 4, 4, 2, 1, 1, 4, 4, 2};
        while(true){
            StringTokenizer st=new StringTokenizer(br.readLine());
            String str=st.nextToken();
            int m=Integer.parseInt(str.charAt(str.length()-1)+"");
            str=st.nextToken();
            int n;
            if(str.length()>1){
                n=Integer.parseInt(str.charAt(str.length()-2)+""+str.charAt(str.length()-1)+"");
            }else{
                n=Integer.parseInt(str.charAt(str.length()-1)+"");
            }
            if(m==0 && n==0 &&str.length()==1){
                break;
            }
            if(m==0 ||m==1 ||m==5 ||m==6){
                sb.append(m).append("\n");
            }else if(n==0){
                if(str.length()==1)
                    sb.append("1\n");
                else{
                    sb.append(modP(m, 4,mods)).append("\n");
                }
            }else{
                sb.append(modP(m, n,mods)).append("\n");
            }
        }
        System.out.print(sb);
    }
   
    static int modP(int m,int n,int[]mods){
        if(n%mods[m]>0)
            n= n%mods[m];
        else
            n=mods[m];
        int res=1;
        for (int i = 0; i < n; i++) {
            res*=m;
        }
        return res%10;
    }
}

UVA - 11426 - GCD - Extreme (II)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        long[]arr=phi(4000001);
        while (true) {
           int x=Integer.parseInt(br.readLine().trim());
           if(x==0)
               break;
           sb.append(arr[x]).append("\n");
        }
        System.out.print(sb);
    }
   
    static long[] phi(int n){
        long[] arr = new long[n+1];
        long[] ans = new long[n];
        arr[1] = 1;
        for (int i = 2; i < n+1; i++) {
            if (arr[i] == 0) {
                arr[i] = i - 1;
                for (int j =2*i; j < n+1; j += i) {
                    if (arr[j] == 0) {
                        arr[j] = j;
                    }
                    arr[j] = arr[j]/i * (i - 1);
                }
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 2*i; j < n; j += i) {
                ans[j] += (i * arr[j / i]);
            }
        }
        for (int i = 2; i < n; i++) {
            ans[i] += ans[i - 1];
        }
        return ans;
    }
}

UVA - 11424 - GCD - Extreme (I) (Java solution)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        long[]arr=phi(200001);
        while (true) {
           int x=Integer.parseInt(br.readLine().trim());
           if(x==0)
               break;
           sb.append(arr[x]).append("\n");
        }
        System.out.print(sb);
    }
   
    static long[] phi(int n){
        long[] arr = new long[n+1];
        long[] ans = new long[n];
        arr[1] = 1;
        for (int i = 2; i < n+1; i++) {
            if (arr[i] == 0) {
                arr[i] = i - 1;
                for (int j =2*i; j < n+1; j += i) {
                    if (arr[j] == 0) {
                        arr[j] = j;
                    }
                    arr[j] = arr[j]/i * (i - 1);
                }
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 2*i; j < n; j += i) {
                ans[j] += (i * arr[j / i]);
            }
        }
        for (int i = 2; i < n; i++) {
            ans[i] += ans[i - 1];
        }
        return ans;
    }
}

UVA - 11424 - GCD - Extreme (I) (C solution)

#include <stdio.h>
#include <math.h>

long* phi(int n){
        long arr [n+1];
        long ans [n];
        int i,j;
        for (i = 0; i < n; i++){
            arr[i]=ans[i]=0;
        }
        arr[n]=0;
        arr[1] = 1;
        for (i = 2; i < n+1; i++) {
            if (arr[i] == 0) {
                arr[i] = i - 1;
                for (j =2*i; j < n+1; j += i) {
                    if (arr[j] == 0) {
                        arr[j] = j;
                    }
                    arr[j] = arr[j]/i * (i - 1);
                }
            }
        }
        for (i = 1; i < n; i++) {
            for (j = 2*i; j < n; j += i) {
                ans[j] += (i * arr[j / i]);
            }
        }
        for (i = 2; i < n; i++) {
            ans[i] += ans[i - 1];
        }
        return ans;
    }

int main()
{
    long* arr=phi(200001);
    int x;
    while(scanf("%d",&x)==1){
        if(x==0)
            break;
        printf("%ld\n",arr[x]);
    }
}

UVA - 583 - Prime Factors

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StringBuffer sb = new StringBuffer("");
        String m = "";
        while(true) {
           int x=Integer.parseInt(br.readLine());
           if(x==0)
               break;
           int[] arr=primeFactors(x);
           sb.append(x).append(" =");
           for(int i=0;i<arr.length;i++){
               if(i>0)
                    sb.append(" x");
               sb.append(" ").append(arr[i]);
           }
            sb.append("\n");
        }
        System.out.print(sb);
    }
   
    static int[] primeFactors(int x){
        LinkedList<Integer> list=new LinkedList<Integer>();
        if(x<0){
            list.add(-1);
        }
        int temp=Math.abs(x);
        boolean notprime=false,entered=false;
        while(temp>1 &&!notprime){
            entered=false;
            for(int i=2;i<Math.sqrt(temp)+1;i++){
                if(temp%i==0){
                    list.add(i);
                    temp/=i;
                    notprime=false;
                    entered=true;
                    break;
                }
            }
            if(!entered)
                 notprime=true;
        }
        if(notprime){
                list.add(temp);
            }
        int[] arr=new int[list.size()];
        for(int i=0;i<arr.length;i++){
            arr[i]=list.get(i);
        }
        return arr;
    }
}

UVA - 10104 - Euclid Problem

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StringBuffer sb = new StringBuffer("");
        String m = "";
        while((m=br.readLine())!=null) {
            StringTokenizer st=new StringTokenizer(m);
            int x=Integer.parseInt(st.nextToken());
            int y=Integer.parseInt(st.nextToken());
            int[] sol=ExtEuc(x, y);
            sb.append(sol[1]).append(" ").append(sol[2]).append(" ").append(sol[0]).append("\n");
        }
        System.out.print(sb);
    }
      

    static int[] ExtEuc(int x, int y) {
        int[] sol = new int[3];
        int tempInt;
        if (y == 0) {
            sol[0] = x;
            sol[1] = 1;
            sol[2] = 0;
        } else {
            tempInt = x / y;
            sol = ExtEuc(y, x % y);
            int temp = sol[1] - sol[2] * tempInt;
            sol[1] = sol[2];
            sol[2] = temp;
        }
         //x=sol[1]   y=sol[2]    GCD=Sol[0]
        return sol;
    }
}

UVA - 10077 - The Stern-Brocot Number System

#include <stdio.h>

int main()
{
    int a,b;
    while(1){
        int xR=1,yR=0,xL=0,yL=1;
        scanf("%d %d",&a,&b);
        if(a==1 && b==1)
            break;
        int tempX=1,tempY=1;
        while(!(a==tempX && b==tempY)){
            if(tempX*b>tempY*a){
                xR=tempX;
                yR=tempY;
                printf("L");
            }else{
                xL=tempX;
                yL=tempY;
                printf("R");
            }
            tempX=xL+xR;
            tempY=yL+yR;
        }
        printf("\n");
    }
    return 0;
}

UVA - 10699 - Count the factors

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
       
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        StringBuffer sb = new StringBuffer("");
        String m = "";
        boolean[] arr=sievePrime(1000*1000);
        while ((m=br.readLine())!=null) {
            if("0".equals(m))
                break;
            int x=Integer.parseInt(m);
            sb.append(x).append(" : ").append(countF(x, arr)).append("\n");
        }
        System.out.print(sb);
    }
   
     static boolean[] sievePrime(int x) {
        boolean[] notPrime = new boolean[x + 1];
        notPrime[0] = true;
        notPrime[1] = true;
        for (int i = 2; i * i < x + 1; i++) {
            if (!notPrime[i]) {
                for (int j = i; i * j < x + 1; j++) {
                    notPrime[i * j] = true;
                }
            }
        }
        return notPrime;
    }
    
     static int countF(int x,boolean[]  arr){
        int count=0,i;
        for(i=1;i<Math.sqrt(x);i++){
           if(x%i==0){
               if(!arr[i])
                count++;
                if(x/i!=i && !arr[x/i]){
                    count++;
                }
           }
        }
        return count;
    }
}

UVA - 374 - Big Mod (C solution)

#include <stdio.h>

int mod(long b, long p, long m)
{
    if(p==0)
        return 1;
    if(p%2==0)
        return (mod(b,p/2,m)*mod(b,p/2,m))%m;
    return (mod(b,p-1,m)*(b%m))%m;
}
int main()
{
    int b,p,m;
    while(scanf("%d %d %d",&b,&p,&m)==3){
        printf("%d\n",mod(b,p,m));
    }
    return 0;
}

UVA - 374 - Big Mod (Java solution)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        StringBuffer sb = new StringBuffer("");
        String m = "";
        boolean flag=false;
        while ((m=br.readLine())!=null) {
            int b=0;
            if("".equals(m))
                b=Integer.parseInt(br.readLine());
            else
                b=Integer.parseInt(m);
            int p=Integer.parseInt(br.readLine());
            int mm=Integer.parseInt(br.readLine());
            flag=true;
            BigInteger bg=BigInteger.valueOf(b);
            bg=bg.modPow(BigInteger.valueOf(p), BigInteger.valueOf(mm));
            sb.append(bg).append("\n");
        }
        System.out.print(sb);
    }
}