For a positive integer n, let’s define a function f:

f(n) = sum of positive integers less than n which are relatively prime to n.

Suppose,

n = 6. So, f(6) = 1 + 5 = 6.

n = 10. So, f(10) = 1 + 3 + 7 + 9 = 20.

Given f(n) you have to find n. If there are multiple answers print any of them.

If there is no answer then just print -1.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of test cases follows. For a single test case, there will be a single integer denoting f(n).

Constraints: 1 ≤ T ≤ 500, 1 <= f(n) <= 10^18

Output For each case, print the answer in a separate line.

Samples:

Input

4
2
3
4
10

Output

-1
3
4
5

Note : x is relatively prime to y if greatest common divisor of x and y is 1.

asked 26 Oct, 12:51

Masud%20Rana's gravatar image

Masud Rana
174

edited 31 Oct, 06:19

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
60618


এখানে ফাংশনটির কাজটা বুঝতে হবে। ফাংশনটির কাজ হল কোনও একটা সংখ্যার ছোট এবং ওই সংখ্যা সাপেক্ষে মৌলিক সংখ্যাগুলোর যোগফল গণনা করা। এখন, একটা সংখ্যা সাপেক্ষে মৌলি বলতে যা বোঝায়-- a এর সাপেক্ষে b প্রাইম হবে যদি এদের মধ্যে ১ ছাড়া অন্য কোন সাধারণ গুণনীয়ক থাকবে না যেমনঃ ৫ এর সাপেক্ষে ৫ এর ছোট মৌলিক সংখ্যাগুলো হলঃ ১,২,৩,৪ । তাহলে f(৫) = ১+২+৩+৪=১০। ইনপুটে যোগফল টা দেয়া থাকবে, n-এর মান প্রিন্ট করতে হবে।

permanent link

answered 27 Oct, 13:52

nishat's gravatar image

nishat
717

edited 31 Oct, 06:34

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
60618

উপরের মন্তব্যকারী ভাইয়া প্রবলেম যেটা ব্যাখ্যা করেছেন সেটাই হবে। তাই ব্যাখ্যা আর করলাম না।
আমার যতটুকু প্রোগ্রামিং জ্ঞান আছে ততটুকু থেকেই একটা কোড লিখলাম এটার জন্য। তবে ২ ইনপুট দিলে কেন -১ আসবে সেটা নিয়ে আমি দ্বিধায় আছি। ভুলগুলো ক্ষমাসুন্দর দৃষ্টিতে দেখবেন। :)

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

int LCS(int n){
    int result =0;
    for(int i = 2; i<=n/2 ; i++){
        if(n%i == 0){
            result = result*10+i;
            n=n/i;
            i--;
        }
    }
    result = result*10+n;
    return result;
}

int isCountable(int a, int n, int result){
    if(a==1){
        return result+1;
    }
    if(a != 1){
        int lcsOfa = LCS(a);
        int lcsOfN = LCS(n);
        int j;
        int counter =0;
        while(lcsOfa%10 >1) {
            lcsOfN = LCS(n);
            while(lcsOfN%10 > 1){
                if(lcsOfN %10 == lcsOfa %10){
                    counter++;
                }
                lcsOfN = lcsOfN/10;
            }
            lcsOfa = lcsOfa/10;
        }
        if(n%a == 0){
            counter++;
        }

        if (counter == 0){
            result = result + a;
            return result;
        }
        else{
           return result + 0;
        }
    }
}

int sumOfRelativePrime(int n){
    int result =0;
    for(int i = 1; i<n; i++){
        result = isCountable(i,n,result);
    }
    printf("final result is %d",result);
}

int main(){
    int n;
    scanf("%d",&n);
    sumOfRelativePrime(n);
}
permanent link

answered 28 Oct, 20:48

Lincoln's gravatar image

Lincoln
111

edited 31 Oct, 06:27

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
60618

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×5

question asked: 26 Oct, 12:51

question was seen: 76 times

last updated: 31 Oct, 06:34