Tính n

View as PDF
Submit solution
Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Dãy số nguyên được xác định theo quy luật như sau:

~x_{0}~ = 1

~x_i~+1 = (a.~x_i~ + ~x_i~ div b) mod c

Đồng chí hãy tìm n nhỏ nhất sao cho tồn tại m < n và ~x_m~ = ~x_n~. Với n không quá 2.~10^7~

Giới hạn: 1 <= a <= ~10^4~ và 1 <= b, c <=~10^{14}~

Dữ liệu vào:

trong một dòng duy nhất chứa 3 số nguyên 1, b, c cách nhau bởi đấu cách.

Dữ liệu ra:

In ra giá trị n tìm được

Input

8 2 31

Output

9

In case the statement didn't load correctly, you can download the statement here: Statement

Comments

Please read the guidelines before commenting.


  • 0
    tcu_18   commented on Aug. 28, 2025, 8:14 a.m.

    include <bits/stdc++.h>

    define ll long long

    define fi first

    define se second

    using namespace std; const ll inf=LLONG_MAX; const ll maxn=1e5+5; main() { ll a, b, c; cin >>a>>b>>c;

    unordered_map<ll,ll> dem;
ll x = 1;
dem[x] = 0; 

for (ll i=1;i<=2e7;i++) {
    x=(a*x+x/b)%c;
    if (dem.count(x)) { 
        cout <&lt;i<< endl;
        return 0;
    }
    dem[x]=i;
}

    }