We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Unfriendly Numbers
  5. Discussions

Unfriendly Numbers

Sort by

recency

|

20 Discussions

|

  • SarahCrim45
     + 0 comments

    This problem is a great way to practice working with divisors and understanding the concept of unique factors. sabexch registration

  • prionkor
     + 0 comments

    With gcd or without gcd, I can not pass last 2 test case due to timeout. Using PHP.

  • siddit
     + 1 comment

    Full Solution in Python:

    I didn't find a single proper solution or even hint in discussion, so I wrote this.

    hint: If factor of f divides an unfriendly number, then factor of f also divides gcd(unfriendly number, f)

    Solution in python:

    import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))

#sets to hold gcds and factors
gcds = set()
factors = set()

#find gcds of f and each unfriendly number
for i in l:
    gcds.add(math.gcd(i, f))


#find factors of f
for i in range(1,math.ceil(math.sqrt(f))):
    if f%i == 0:
        factors.add(i)
        factors.add(f//i)

# keeps count of number of factors not dividing unfriendly numbers
ans = 0

#find those numbers
for i in factors:
    for j in gcds:
        if j%i == 0:
            break
        else:
            continue
    
    else:
        ans+=1

print(ans)

  • robin_vezina
     + 0 comments

    Java 8

    import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.LongStream;

public class Solution {

  static long gcd(final long a, final long b) {
    return b == 0 ? a : gcd(b, a % b);
  }

  public static void main(String args[]) {
    try (final Scanner scanner = new Scanner(System.in)) {
      final int n = scanner.nextInt();
      final long f = scanner.nextLong();

      final LinkedList<Long> factors = new LinkedList<>();
      for (long i = 1; i * i <= f; i++) {
        if (f % i == 0) {
          factors.add(i);
          if (i * i != f) {
            factors.add(f / i);
          }
        }
      }

      LongStream.generate(scanner::nextLong).limit(n).map(u -> gcd(u, f)).distinct().forEach(gcdU -> {
        for (final Iterator<Long> i = factors.iterator(); i.hasNext();) {
          if (gcdU % i.next() == 0) {
            i.remove();
          }
        }
      });

      System.out.println(factors.size());
    }
  }
}

  • qwrtyuiuytres
     + 2 comments
    #include <bits/stdc++.h>
using namespace std;

// function to get gcd
int gcd(long int a, long int b){
    if(b==0){
        return a;
    }else{
        return gcd(b, a%b);
    }
}

int main(){
// n,f and temp variable t
    long int n, f, t;
    cin>>n>>f;
    long int root = (int)sqrt(f)+1;
    set<long int> factors, arr;
    for(long int i=1; i<root; i++){
        if(f%i==0){
            factors.insert(i);
            factors.insert((long int)f/i);
        }
    }

    for(int i=0; i<n; i++){
		// get value and insert gcd of value and f
        cin>>t;
        arr.insert(gcd(t, f));
    }

    for(auto i=arr.begin(); i!=arr.end(); i++){
        for(auto it=factors.begin(); it!=factors.end(); it++){
            if((*i)%(*it)==0){
						// remove all factors which divides any value
                factors.erase(it);
            }
        }
    }
		// print remaining factors
    cout<<factors.size()<<endl;
    return 0;
}