Найти последнюю цифру a^b

@diagon · Регистрация: 02.05.2010

Author24 — интернет-сервис помощи студентам

В input.txt лежат а и b-число и степень.
В output.txt нужно вывести последнюю цифру a^b.
a и b не превышают 10000.
Должно быть какое-то простое решение, но я не могу до него додуматься...
Есть, конечно, закономерности, например 54 в нечетной степени оканчивается на 4, а в четной на 6, но беда в том, что для каждого числа эти закономерности разные...
Выявлять эти закономерности или умножать числа, хранящиеся в строках слишком муторно, должно быть более простое решение...

@~~IrineK~~ · 10.04.2011, 16:58

Самое простое: взять последнюю цифру а и ее возводить в степень.
Потом от результата брать последнюю цифру.

@diagon · 10.04.2011, 17:02 **[ТС]**

Видел такое, но, к примеру, 24 в 9й степени оканчивается на 4.
По такому алгоритму берем 4, возводим в квадрат, получаем 16.
Берем последнюю цифру-6, возводим в квадрат, получаем 36.
Из 6 будет получатся 36, это замкнутый круг, и четверки в нем не видно.

@~~IrineK~~ · 10.04.2011, 17:09

Значит, нужно выявлять закономерности.
Одна - налицо: что закачивается на 0,1,5,6 - в любой степени на них и заканчивается
Все остальное - к этому приводится через несколько шагов.

@easybudda · 10.04.2011, 17:10

diagon, Всё проще

C

1	printf("%d", (int)pow((double)(a % 10), (double)b)) % 10);

@diagon · 10.04.2011, 17:16 **[ТС]**

Сообщение от easybudda

diagon, Всё проще

C

1	printf("%d", (int)pow((double)(a % 10), (double)b) % 10);

Хм... Не совсем понятен алгоритм
Зачем возводить в степень последние числа?

Добавлено через 3 минуты
Все, дошло.
Спасибо!

@easybudda · 10.04.2011, 17:20

diagon, для слишком больших степеней работать скорее всего не будет, разве что раскладывать показатель степени на множетели и методично возводить в их степень последнюю цифру... Ну или хитрый математически-акробатический этюд нужен... Больше всего не понятно, как результаты проверять.
Кстати, обратите внимание - я там сначала скобку одну пропустил, потом поправился...

@~~IrineK~~ · 10.04.2011, 17:31

Закономерности:
2: 2,4,8,6 - период
3: 3,9,7,1
4: 4,6
7: 7,9,3,1
8: 8,4,2,6
9: 9,1

0,1,5,6 - все время остаются

Осталось только case написать ))

@diagon · 10.04.2011, 17:34 **[ТС]**

К сожалению, там слишком большие степени.
Через закономерности однако проще будет...

@Nameless One · 10.04.2011, 18:16

C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int get_unsigned(const char*, size_t*);
size_t my_pow(size_t, size_t);
 
int main(int argc, char* argv[])
{
    size_t base, exp, result;
    
    if(argc != 3)
    fprintf(stderr, "Usage: %s BASE EXP\n", *argv), exit(1);
    
    if(!get_unsigned(argv[1], &base))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[1]), exit(1);
 
    if(!get_unsigned(argv[2], &exp))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[2]), exit(1);
 
    result = my_pow(base, exp);
    
    printf("Last digit of %u ^ %u is %u\n", base, exp, result);
    
    exit(0);
}
 
int get_unsigned(const char* buf, size_t* result)
{
    static char* endptr;
    long int temp;
 
    temp = strtol(buf, &endptr, 10);
 
    if(temp == LONG_MIN || temp == LONG_MAX || !(*buf != '\0' && *endptr == '\0') || temp < 0)
    {
    *result =0;
    return 0;
    }
 
    *result = (size_t) temp;
 
    return 1;
}
 
size_t my_pow(size_t base, size_t exp)
{
    size_t result = 1;
 
    base %= 10;
            
    while(exp--)
    {
    result *= base;
    result %= 10;
    }
 
    return result;
}

Вот вариант с тупым перемножением. Работает, естественно, и для больших степеней

@Nameless One · 10.04.2011, 18:43

Вот немного улучшенный вариант функции my_pow (невооруженным глазом заметно, что на больших степенях работает быстрее). Заметь, что теперь функция принимает уже последнюю цифру от числа-основания степени, а не само основание (см. строку 21):

C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int get_unsigned(const char*, size_t*);
size_t my_pow(size_t, size_t);
 
int main(int argc, char* argv[])
{
    size_t base, exp, result;
    
    if(argc != 3)
    fprintf(stderr, "Usage: %s BASE EXP\n", *argv), exit(1);
    
    if(!get_unsigned(argv[1], &base))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[1]), exit(1);
 
    if(!get_unsigned(argv[2], &exp))
    fprintf(stderr, "%s is not a legal unsigned integer\n", argv[2]), exit(1);
 
    result = my_pow(base % 10, exp);
    
    printf("Last digit of %u ^ %u is %u\n", base, exp, result);
    
    exit(0);
}
 
int get_unsigned(const char* buf, size_t* result)
{
    static char* endptr;
    long int temp;
 
    temp = strtol(buf, &endptr, 10);
 
    if(temp == LONG_MIN || temp == LONG_MAX || !(*buf != '\0' && *endptr == '\0') || temp < 0)
    {
    *result =0;
    return 0;
    }
 
    *result = (size_t) temp;
 
    return 1;
}
 
size_t my_pow(size_t base, size_t exp)
{
    size_t temp;
 
    if(exp == 0)
    return 1;
        
    if(exp & 1)
    return (my_pow(base, exp - 1) * base) % 10;
    
    temp = my_pow(base, exp / 2);
    return (temp * temp) % 10;
}

@Nameless One · 10.04.2011, 18:49

UPD: исправил my_pow в предыдущем сообщении (все из-за невнимательности

)

@~~IrineK~~ · 10.04.2011, 18:56

Обошлось без case:

C++

#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
 
int main()
{   string A;
    long B;
    int N;
 
while(1)
{   cout<<"A = ";  //число - оочень большое
    getline(cin,A);
    cout<<"B = "; //степень - поменьше, от 1 и выше
    cin>>B;
    N = A[A.length()-1]-'0';
    B %= 4;
    if(!B) B=4;
    
    N = (int)pow(1.0*N,B)%10;
 
    cout<<"last digit: "<<N<<"\n";
    cin.sync();
}
    return 0;
}

@Nameless One · 10.04.2011, 19:06

IrineK, нулевую степень неправильно обрабатывает:

Код

A = 34
B = 0
last digit: 6

Может, лучше как-то так:

C++

if(!B)
{
        cout<<"last digit: 1\n";
        continue;
}

?

@~~IrineK~~ · 10.04.2011, 19:08

Специально написала в комментах:
от 1 и выше
Для нулевой степени - допишите пару строк.

@Nameless One · 10.04.2011, 19:10

Не по теме:

О, не заметил...

@diagon · 10.04.2011, 19:11 **[ТС]**

А нулевой и нету, минимальная-один.
Спасибо всем.

@~~IrineK~~ · 10.04.2011, 21:34

С учетом нулевой степени )):

C++

#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
 
int main()
{   string A;
    long B;
    int N;
 
while(1)
{   cout<<"A = ";  //число - оочень большое
    getline(cin,A);
    cout<<"B = "; //степень - поменьше, от 0 и выше
    cin>>B;
    if(!B) 
    {   cout<<"last digit: "<<1<<"\n";
        cin.sync();
        continue;
    }
 
    N = A[A.length()-1]-'0';
    B %= 4;
    if(!B) B=4;
    
    N = (int)pow(1.0*N,B)%10;
 
    cout<<"last digit: "<<N<<"\n";
    cin.sync();
}
    return 0;
}

Добавлено через 2 часа 20 минут
В строке 17 корректней будет:

C++

1	cout<<"last and the only one digit: "<<1<<"\n";

))

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	10.04.2011, 18:49	12
	UPD: исправил my_pow в предыдущем сообщении (все из-за невнимательности ) 1

@~~IrineK~~ Заблокирован
	10.04.2011, 19:08	15
	Специально написала в комментах: от 1 и выше Для нулевой степени - допишите пару строк. 2

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
		1
	Найти последнюю цифру a^b 10.04.2011, 16:55. Показов 8335. Ответов 17 Метки нет (Все метки) В input.txt лежат а и b-число и степень. В output.txt нужно вывести последнюю цифру a^b. a и b не превышают 10000. Должно быть какое-то простое решение, но я не могу до него додуматься... Есть, конечно, закономерности, например 54 в нечетной степени оканчивается на 4, а в четной на 6, но беда в том, что для каждого числа эти закономерности разные... Выявлять эти закономерности или умножать числа, хранящиеся в строках слишком муторно, должно быть более простое решение... 0

@~~IrineK~~ Заблокирован
	10.04.2011, 16:58	2
	Самое простое: взять последнюю цифру а и ее возводить в степень. Потом от результата брать последнюю цифру. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	10.04.2011, 17:02 [ТС]	3
	Видел такое, но, к примеру, 24 в 9й степени оканчивается на 4. По такому алгоритму берем 4, возводим в квадрат, получаем 16. Берем последнюю цифру-6, возводим в квадрат, получаем 36. Из 6 будет получатся 36, это замкнутый круг, и четверки в нем не видно. 0

@~~IrineK~~ Заблокирован
	10.04.2011, 17:09	4
	Значит, нужно выявлять закономерности. Одна - налицо: что закачивается на 0,1,5,6 - в любой степени на них и заканчивается Все остальное - к этому приводится через несколько шагов. 1

@easybudda Модератор 12458 / 7482 / 1753 Регистрация: 25.07.2009 Сообщений: 13,762
	10.04.2011, 17:20	7
	diagon, для слишком больших степеней работать скорее всего не будет, разве что раскладывать показатель степени на множетели и методично возводить в их степень последнюю цифру... Ну или хитрый математически-акробатический этюд нужен... Больше всего не понятно, как результаты проверять. Кстати, обратите внимание - я там сначала скобку одну пропустил, потом поправился... 1

@~~IrineK~~ Заблокирован
	10.04.2011, 17:31	8
	Закономерности: 2: 2,4,8,6 - период 3: 3,9,7,1 4: 4,6 7: 7,9,3,1 8: 8,4,2,6 9: 9,1 0,1,5,6 - все время остаются Осталось только case написать )) 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	10.04.2011, 17:34 [ТС]	9
	К сожалению, там слишком большие степени. Через закономерности однако проще будет... 0

@Nameless One
	10.04.2011, 19:10 #16
	Не по теме: О, не заметил... 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	10.04.2011, 19:11 [ТС]	17
	А нулевой и нету, минимальная-один. Спасибо всем. 0