e-olymp 442. Построения

29/11/2017 by Данилов Андрей

Задача

Иван Петрович преподает в школе физкультуру, но интересуется также математикой, в основном, с практической точки зрения. Например, его интересует вопрос, сколько различных построений существует для группы из [latex]N[/latex] человек. Иван Петрович выяснил, что если [latex]N[/latex]– простое число, то получается только [latex]2[/latex] построения: в колонну по одному ([latex]1[/latex]×[latex]N[/latex]) и в шеренгу ([latex]N×1[/latex]). Эти тривиальные построения возможны для любого [latex]N[/latex] > [latex]1[/latex] (для [latex]N = 1[/latex] существует только одно построение ([latex]1×1[/latex]), которое не является ни шеренгой, ни колонной). Если [latex]N[/latex] – составное число, то существует и другие нетривиальные построения. Для [latex]100[/latex] человек существует девять построений: ([latex]1×100[/latex]), ([latex]2×50[/latex]), ([latex]4×25[/latex]), ([latex]5×20[/latex]), ([latex]10×10[/latex]), ([latex]20×5[/latex]), ([latex]25×4[/latex]), ([latex]50×2[/latex]) и ([latex]100×1[/latex]).

Входные данные

В первой строке ввода содержится одно целое число [latex]N[/latex] (1 ≤[latex]N[/latex]≤ 109).

Выходные данные

Вывести одно целое число – количество различных построений для группы из [latex]N[/latex] человек.

Тесты

#	Входные данные	Выходные данные
1	100	9
2	1	1
3	6	4
4	999983	2
5	2	2

Код программы

#include <iostream>
#include <cmath>
using namespace std;

int main () { 
    int NumberOfPeople;
    cin >> NumberOfPeople;
    if(NumberOfPeople == 1){
        cout << 1;
        return 0;
    } 
    else
    {
          int deviders = 0;
          for(int i = 1; i < sqrt(NumberOfPeople);i++){
                if(NumberOfPeople % i == 0) deviders++; // проверка на делимость
    }
    deviders *= 2;
    int Root = sqrt(NumberOfPeople);
    if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость
    cout << deviders;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main () {

int NumberOfPeople;

cin >> NumberOfPeople;

if(NumberOfPeople == 1){

cout << 1;

return 0;

}

else

{

int deviders = 0;

for(int i = 1; i < sqrt(NumberOfPeople);i++){

if(NumberOfPeople % i == 0) deviders++; // проверка на делимость

}

deviders *= 2;

int Root = sqrt(NumberOfPeople);

if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость

cout << deviders;

}

return 0;

}

Решение задачи

По условию задачи требуется найти все возможные построения. Это значит, что мы должны найти все возможные варианты разбиения числа на множители. Для этого можно обойтись перебором всех делителей числа от 1 до корня из этого числа, а затем умножить полученное значение на 2 так как для нас имеет значение порядок делителей. Если корень из числа есть делитель данного числа то увеличиваем счетчик на 1.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

A322. Максимальная сумма делителей

17/12/2016 by Валентина Андриеш

Задача. Найти натуральное число с максимальной суммой делителей на заданном промежутке.

Входные данные:
— [latex]n[/latex] — промежуток чисел(от 1 до [latex]n[/latex]);

Выходные данные:
— [latex]max[/latex] _ [latex]sum[/latex] — максимальная сумма делителей числа на этом промежутке;
— [latex]max[/latex] _ [latex]number[/latex] — натуральное число с этой суммой;

Тесты:

[latex]n[/latex]	[latex]max[/latex] _ [latex]number[/latex]	[latex]max[/latex] _ [latex]sum[/latex]
100	96	252
8743	8400	30752
23000	22680	87120

Код на языке C++:

#include <iostream>
#include <cmath>
using namespace std;
 
int sum_dividers(int n){
    int sum=0;
    for(int i=1; i<sqrt(n); i++){
        if((n%i)==0)sum+=i+(n/i);
    }
    int i=sqrt(n);
    if(i*i==n)sum+=i;
    return sum;
}
 
int main() {
    int n;
    cin>>n;
    int max_sum=0;
    int max_number=0;
    int j;
    for(j=1; j<=n; j++){
        int s=sum_dividers(j);
        if(max_sum<s){
            max_sum=s;
            max_number=j;
        }
    }
    cout<<max_number<<" "<<max_sum;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int sum_dividers(int n){

int sum=0;

for(int i=1; i<sqrt(n); i++){

if((n%i)==0)sum+=i+(n/i);

}

int i=sqrt(n);

if(i*i==n)sum+=i;

return sum;

}

int main() {

int n;

cin>>n;

int max_sum=0;

int max_number=0;

int j;

for(j=1; j<=n; j++){

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

cout<<max_number<<" "<<max_sum;

return 0;

}

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    static int sum_dividers(int n){
        int sum=0;
            for(int i=1; i<Math.sqrt(n); i++){
                    if((n%i)==0)sum+=i+(n/i);
            }
            double i=Math.round(Math.sqrt(n));
            if(i*i==n)sum+=i;
            return sum;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int max_sum=0;
        int max_number=0;
        int j;
        for(j=1; j<=n; j++){
            int s=sum_dividers(j);
            if(max_sum<s){
                        max_sum=s;
                        max_number=j;
            }
        }
        System.out.println(max_number+" "+max_sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static int sum_dividers(int n){

int sum=0;

for(int i=1; i<Math.sqrt(n); i++){

if((n%i)==0)sum+=i+(n/i);

}

double i=Math.round(Math.sqrt(n));

if(i*i==n)sum+=i;

return sum;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int max_sum=0;

int max_number=0;

int j;

for(j=1; j<=n; j++){

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

System.out.println(max_number+" "+max_sum);

}

Решение задачи:
Для нахождения суммы делителей используется функция [latex]sum[/latex] _ [latex]dividers[/latex], которая в созданном цикле сначала находит все делители числа, а после суммирует их, присваивая значение переменной [latex]sum[/latex]. Создав в главной функции [latex]main[/latex] еще один цикл со счетчиком от 1 до [latex]n[/latex], подставляю в предыдущую функцию [latex]sum[/latex] _ [latex]dividers[/latex] все натуральные числа на выбранном промежутке. C помощью свободных переменных [latex]max[/latex] _ [latex]sum[/latex] и [latex]max[/latex] _ [latex]number[/latex] нахожу максимальное значение сумм и соответствующее ему натуральное число.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 322

Related Images:

Функция Эйлера

01/07/2016 by Лена Наумова

Условие

В теории чисел известна функция Эйлера $latex \varphi(n)$ — количество чисел, меньших $latex n$ и взаимно простых с ним. Напомним, два числа взаимно просты, если у них нет общих делителей, кроме единицы.

Расширим понятие функции Эйлера на строки. Пусть $latex s$ — непустая строка над алфавитом {$latex a$ .. $latex z$}, а $latex k$ — целое положительное число. Тогда $latex s \cdot k$ по определению — строка $latex t = \underbrace{s \circ s \circ \ldots \circ s}_{\text{k}}$ (конкатенация $latex s$ самой с собой $latex k$ раз). В таком случае будем говорить, что строка $latex s$ — делитель строки $latex t$. Например, «ab» — делитель строки «ababab».

Две непустые строки $latex s$ и $latex t$ будем называть взаимно простыми, если не существует строки $latex u$ такой, что она — делитель и для $latex s$, и для $latex t$. Тогда функция Эйлера $latex \varphi(s)$ для строки $latex s$ по определению — количество непустых строк над тем же алфавитом {$latex a$ .. $latex z$}, меньших $latex s$ по длине, и взаимно простых с ней.

Входные данные

Во входном файле дана строка $latex s$ длиной от $latex 1$ до $latex 10^5$ символов включительно, состоящая из маленьких латинских букв.

Выходные данные

Вычислите значение $latex \varphi(s)$ и выведите единственное число — остаток от его деления на $latex 1000000007 (10^9 + 7)$.

Решение

Очевидно, что когда строка $latex s$ длины $latex n$ не имеет делителей, кроме самой себя, любая строка длины меньшей, чем $latex n$, будет взаимно простой с $latex s$. Тогда достаточно посчитать количество всех возможных строк длины от $latex 1$ до $latex n-1$ включительно. Для некоторого $latex k$ количество строк этой длины будет равно $latex 26^k$. Тогда количество $latex m$ всех возможных строк длины от $latex 1$ до $latex n-1$ будет вычисляться по следующей формуле: $latex m=\sum\limits_{k=1}^{n-1} 26^k$.

Теперь рассмотрим случай, когда строка имеет делители. Поскольку строка $latex s$ в таком случае является конкатенацией некоторого количества одинаковых строк меньшей длины, найдём эту самую подстроку, кторая является минимальным (кратчайшим) делителем строки $latex s$. Для этого воспользуемся префикс-функцией. Она возвращает вектор $latex pi$ значений для всех подстрок строки $latex s$, которые являются префиксами $latex s$, где значение — максимальная длина префикса строки, совпадающего с её суффиксом. Тогда на $latex n-1$-ом месте вектора $latex pi$ будет стоять длина наибольшего префикса строки $latex s$, а оставшийся «кусочек» строки $latex s$ будет представлять собой минимальный делитель.

Осталось вычислить количество строк, которые не взаимно просты с $latex s$. Пусть k — длина минимального делителя $latex s$. Тогда все строки, являющиеся конкатенациями этого делителя, не будут взаимно простыми с $latex s$. Для подсчёта их количества достаточно поделить длину исходной строки на k, но ответ будет на единицу меньше, поскольку в этой формуле учитывается и сама строка $latex s$, как собственный делитель.

Для окончательного ответа на задачу остаётся вычесть из общего количества строк количество не взаимно простых с $latex s$.

Тесты

№	Входные данные	Выходные данные
1	aa	25
2	abab	18277
3	abcdefgh	353082526
4	aaaaaab	321272406
5	aaaaaaa	321272406

Программный код

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9+7;

vector<int> prefix_function(string s) {
    int n = s.length();
    vector<int> pi(n);
    pi[0] = 0;
    for(int i = 1; i < n; i++){
        int j = pi[i - 1];
        while(j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if(s[i] == s[j])
            j++;
        pi[i] = j;  
    }
    return pi;
}

int main() {
    string s;
    cin >> s;
    int n = s.length();
    long long mul = 26, ans = 0;
    for(int i = 1; i < n; i++, mul *= 26, mul %= MOD)
        ans += mul;
    vector<int> pi = prefix_function(s);
    int k = n - pi[n - 1];
    if(n % k == 0){
        ans -= n / k - 1;   
    }
    cout << ans % MOD;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

const int MOD = 1e9+7;

vector<int> prefix_function(string s) {

int n = s.length();

vector<int> pi(n);

pi[0] = 0;

for(int i = 1; i < n; i++){

int j = pi[i - 1];

while(j > 0 && s[i] != s[j])

j = pi[j - 1];

if(s[i] == s[j])

j++;

pi[i] = j;

}

return pi;

}

int main() {

string s;

cin >> s;

int n = s.length();

long long mul = 26, ans = 0;

for(int i = 1; i < n; i++, mul *= 26, mul %= MOD)

ans += mul;

vector<int> pi = prefix_function(s);

int k = n - pi[n - 1];

if(n % k == 0){

ans -= n / k - 1;

}

cout << ans % MOD;

return 0;

}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: делители

e-olymp 442. Построения

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки

Related Images:

A322. Максимальная сумма делителей

Related Images:

Функция Эйлера

Related Images: