Intereting Posts

Минимальное положительное целое число, делящееся на n

Для данного числа n найдем минимальное положительное целое число, делящееся на n, с суммой цифр, равной n.

Я много искал, а также получил некоторый ответ на этот вопрос, но это нелегко понять для меня. Я новый программист и люблю писать на языке программирования C. Вот почему я буду рад, если кто-нибудь поможет мне найти решение этой проблемы на C. Как я когда-либо пробовал, и мой код не работает для большого ввода n. такой, что n = 999. Мой код здесь:

#include  #include  long long int summingDigit(long long int dividend); int main() { long long int n, dividend, add, ans; int i, test, c; scanf("%d", &test); for(c=1; c<=test; c++) { scanf("%lld", &n); for(i=1; ; i++) { dividend = n*i; add = summingDigit(dividend); if(add==n) { ans=dividend; break; } } printf("%lld\n", dividend); } return 0; } long long int summingDigit(long long int dividend) { long long int sum=0, rem; while(dividend!=0) { rem=dividend%10; dividend=dividend/10; sum=sum+rem; } return sum; } 

На самом деле я желаю результата: для n = 1, result = 1 для n = 10, result = 190 Для объяснения результата содержится 3 цифры. и их сумма 1 + 9 + 0 = 10, равная n (10). Надежда все в состоянии понять.

Пожалуйста, дайте мне лучший способ экономии времени на эту проблему. Потому что мое решение займет слишком много времени. Но я не понимаю других языков программирования. Поэтому, пожалуйста, объясните это на C легко. Спасибо, что помогли мне в продвижении.

Я нашел решение, но не понимаю. Пожалуйста, позвольте мне понять всю программу, если у вас есть достаточно времени.

 #include #include #include using namespace std; #define F first #define S second #define N 1100 #define mp make_pair queue<pair >Q; short sumTrace[N][N], mulTrace[N][N]; void print(int sum, int mul) { if (sumTrace[sum][mul] == 42)return; print(sum-sumTrace[sum][mul], mulTrace[sum][mul]); printf("%d",sumTrace[sum][mul]); } void solve(int n) { Q.push(mp(0,0)); sumTrace[0][0]=42; // any number greater than 9 while (1) { int sum = Q.front().F; int mul = Q.front().S; if (sum == n && mul == 0) break; Q.pop(); for (int i=0; i n)break; int nmul = (mul*10+i)%n; if (sumTrace[nsum][nmul] == -1) { Q.push(mp(nsum, nmul)); sumTrace[nsum][nmul] = i; mulTrace[nsum][nmul] = mul; } } } print(n,0); while(!Q.empty())Q.pop(); } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); memset(sumTrace, -1, sizeof sumTrace); solve(n); printf("\n"); } return 0; } в #include #include #include using namespace std; #define F first #define S second #define N 1100 #define mp make_pair queue<pair >Q; short sumTrace[N][N], mulTrace[N][N]; void print(int sum, int mul) { if (sumTrace[sum][mul] == 42)return; print(sum-sumTrace[sum][mul], mulTrace[sum][mul]); printf("%d",sumTrace[sum][mul]); } void solve(int n) { Q.push(mp(0,0)); sumTrace[0][0]=42; // any number greater than 9 while (1) { int sum = Q.front().F; int mul = Q.front().S; if (sum == n && mul == 0) break; Q.pop(); for (int i=0; i n)break; int nmul = (mul*10+i)%n; if (sumTrace[nsum][nmul] == -1) { Q.push(mp(nsum, nmul)); sumTrace[nsum][nmul] = i; mulTrace[nsum][nmul] = mul; } } } print(n,0); while(!Q.empty())Q.pop(); } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); memset(sumTrace, -1, sizeof sumTrace); solve(n); printf("\n"); } return 0; } 

Одна небольшая возможная оптимизация может быть следующей:

Вы можете использовать здесь немного математики.

Если существует такое i , что сумма цифр n*i равна n , то:

 Say n*i = p + 10q + 100r + 1000s +... (where p, q, r, s are digits of n*i) Then p + q + r + s ... = n. Hence n * (i-1) = 9q + 99r + 999s +... (after subtracting n from both sides) = 9 * (q + 11r + 111s +... ) 

Следовательно, вы заметите, что n * (i-1) всегда будет кратным 9 .

Поэтому, если n изначально не кратно 9, вы можете пропустить много возможных кандидатов, выполнив шаги из 9 ( i += 9 ) вместо 1 ( i++ ).

Вы можете думать об этом, и вы можете придумать что-то лучшее.

Что-то вроде этого? , ОЦ

 m=n+1; while (summingDigit(m)!=n && m%n!=0) m++; 

Или, как вы это сделали.

 m=2*n; while (summingDigit(m)!=n) m+=n;