[알고리즘] 백준 4375 1 // 모듈러연산, str금지, 자릿수저장할 변수

* 풀이1

• 1, 11, 111, ....을 str로 구함 -> 숫자 * 10 +1 으로 대체가능
• 예시에서 12자리는 long long의 범위를 벗어남 -> 직접 num을 구하기 금지, 모듈러 연산을 이용

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n;
ll ret;
vector<ll> nums;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string str="1";
    for(int i=0;i<10;++i) {
        nums.push_back(stol(str));
        str+="1";
    }

    for(auto i : nums) {
        cout<<i<<" ";
    }
    
    while(cin>>n) {
        for(auto num : nums) {
            if(n<=num && num%n == 0) {
                cout<<to_string(num).size()<<"\n";
                break;
            }
        }
    }
    
    
}

 

* 풀이2

• 구하는것 : num % n == 0 이되는 n의 자릿수
• 자릿수를 저장할 변수 필요 (str. size() 금지)
• +, * 로 이루어진숫자는 중간중간에 모듈러 연산을 해도 결과가 동일하다! -> num을 진짜 구할 필요 X

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
      
    ll n;
    while(cin>>n) {  
        ll num = 1, ret = 1; // num, 자릿수
        while(1) {
            if(num % n == 0) {
                cout << ret << "\n";
                break;
            }
            ret++;
            num = (num * 10 + 1) % n;     // 모듈러 연산 사용
        }
    }

    return 0;
}