Свойства чисел

[Hennessy]

Уважаемые программисты!
Очень нуждаюсь в Вашей помощи. Я получил следующее задание. Написать на C# программу: "Вводятся два числа N и K. Необходимо вывести количество чисел в промежутке от 1 до N, сумма цифр которых делится нацело на K". Долго бился, пытаясь найти Великую закономерность, которая решит все проблемы, но так и не нашел. Прошу Вас высказывать любые свои мыслишки касательно этой задачи. Заранее благодарю

[Вадим Мошев]

Может просто имеет смысл написать функцию для нахождения такой суммы чисел?

[Hennessy]

Сообщение от Вадим Мошев

Может просто имеет смысл написать функцию для нахождения такой суммы чисел?

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

[Alkagolik]

верхняя граница N должна быть определена. Интересная, вроде не сложная задачка. Посижу покумекаю что к чему. Но приблизительно так
если N>1000 000
целая равняется N/1000 000;
1000 000 /10;
tmp=N mod 1000 000

[G-Kyller]

int N=0, K=0;
            int kolvo = 0;
            int[] mass = new int[1];
            int summ = 0;
            N = Convert.ToInt32(Console.ReadLine());
            K = Convert.ToInt32(Console.ReadLine());
            for (int i = 1; i <= N; i++)
            {
                mass[0] = i;
                summ = mass.Sum();
                //string cifra = i.ToString();//Вместо summ = mass.Sum();(работает медленней)
                //for (int j = 0; j < cifra.Length; j++) { summ += cifra[j]; }//Поэтому заменено
                if (summ % K == 0) { kolvo++; }
            }
            Console.WriteLine("Количество чисел: {0}", kolvo);
            Console.ReadLine();

При N в несколько миллионов считает легко, но в районе 5 000 000 и более уже становится видно задержку
P.S. Самому уже интересно как это сделать быстро при больших числах))

[Hennessy]

верхняя граница N должна быть определена.

Нет, по условию и N и K - любые числа.

если N>1000 000
целая равняется N/1000 000;
1000 000 /10;
tmp=N mod 1000 000

Честно говоря, не уловил=). Что за "целая" такая?

G-Kyller, наверное это покажется странным, но мне не доводилось встречаться с таким кодом=). А именно с

N = Convert.ToInt32(Console.ReadLine()

,

summ = mass.Sum()

и

string cifra = i.ToString()

.
Если можно в двух словах=)

P.S. Самому уже интересно как это сделать быстро при больших числах))

=))

[G-Kyller]

N = Convert.ToInt32(Console.ReadLine());

С консоли всегда вводится строка, поэтому чтобы получить цифру, надо использовать конвертер

summ = mass.Sum();

У массивов и листов есть функция Sum(), которая возвращает сумму цифр данного элемента

string cifra = i.ToString()

Если не использовать массив, то получение суммы цифр можно найти считывая по одному символу цифры, для этого надо работать со строкой, а не самой цифрой, вот мы и получаем число как строку

[Alkagolik]

ну вот как бэ на с++ есть такая штука, главное в типы вложиться... или обработать исключение

#include <iostream>
#include <math.h>
//Вводятся два числа N и K.
//Необходимо вывести количество чисел в промежутке 
//от 1 до N, сумма цифр которых делится нацело на K

int SUM_RAZR( unsigned int chislo);
int DELENIE(int a, int b);

int main ()
{
	unsigned int N;
	int k;
	std::cout <<"push N: ";
	std::cin >> N;
	std::cout << "push k: ";
	std::cin >> k;
	for (unsigned int i=0; N>=i;i++)
	{
		if (SUM_RAZR(i)%k==0){
			std::cout <<i << ", ";
		}
	}
	return 0;
}
//функция подсчета всех цифр числа
int SUM_RAZR( unsigned int chislo)
{
	int tmp=0, in=10, bufer=0;
	double stepen=10;
	do{
		if ((chislo >= pow (10, stepen))&&(chislo < pow (10, stepen+1))){
			tmp += chislo / pow (in, stepen);
			chislo = DELENIE(chislo, pow (10, stepen));
			stepen--;
		}
		else stepen --;
	}while (stepen!=-1);
	return tmp;
}
// остаток от деления
int DELENIE(int a, int b)
{
	return (a%b);
}

Хотя я только что попробовал разложить число (не помню точно) 465465487... НУ ОЧЕНЬ длинный ряд получается.

[Hennessy]

G-Kyller, спасибо, буду знать.
Alkagolik, я изучил только С#, поэтому абсолютно не ориентируюсь в Вашем коде.
Мне тут прислали вариантец, но он работает с ошибкой(при вводе N=22 K=4 выдает ответ 4 вместо 5). Прошу Вас глянуть. Кстати, вариантец этот - хороший пример того кода, который мне понятен

#include <stdio.h>
#include <stdlib.h>
int main(){
int i,j=0,n,tmp,k,z,sum;
scanf("%i %i",&n,&k);
for (i=1;i<n;i++)
{
z=i;
sum=0;
while (z)
{
sum+=(z%10);
z/=10;
}
if ((sum%k)==0)
j++;
}
printf("%d",j);
return 0;
}

[Hennessy]

Нашел ошибку - в условии цикла проверялись все числа до N-1.
Вот исправленный вариант для потомков:

#include <stdio.h>
#include <stdlib.h> /* Ввод N и K. Найти количество чисел в промежутке от 1 до N, сумма цифр которых делится на К*/
int main()
{
int N,K;
int i,count,key,SummaCifr;
count=0;
scanf("%d %d",&N,&K);
for (i=1;i<(N+1);i++)
{
key=i;
SummaCifr=0;
while (!(key==0))
{
SummaCifr=SummaCifr+(key%10);
key=key/10;
}
if ((SummaCifr%K)==0)
count++;
}
printf("%d",count);
return 0;
}

Пускай этот код не очень быстрый, но зато четкий и ясный)
я свою миссию выполнил, основываясь на Ваших дельных предложениях. Спасибо всем за помощь!