11574: 【原1574】调皮的助教

题目

题目描述

author: Mickeypeng 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1574

Description

n个助教（编号从0到n-1）给大家出题。 每次作业每人出一道题，也就是说，每次作业有n个题，题目的编号也为0到n-1。 最初，第0号助教出的题题号为0，第1号助教出的题题号为1，……，依此类推。 但是，助教们觉得一直这样也没有意思，于是，他们制定了如下规则：

每出完一次作业后，出第0号题的助教改出第m号题，出第1号题的助教改出第m+1号题，……， 依此类推，出第n−m号题目的助教改出第0号题，出第n-m+1号题目的助教改出第1号题目，……， 出第n-1号题目的助教改出第m-1号题。

现在，一共出了10^k(10的k次方)次作业，请问x号助教下次出题的题号。

Input Format

输入共1行，包含4个整数n、m、k、x每两个整数之间用一个空格隔开。

Output Format

输出共1行，包含1个整数，表示10^k(10的k次方)轮后x号助教下次出题的题号。

Sample Input

10 3 4 5

Sample Output

5

Limits

• 对于30%的数据，0<𝑘<7；
• 对于80%的数据，0<𝑘<107；
• 对于100%的数据，1<𝑛<1,000,000，0<𝑚<𝑛，1≤x≤n，0<𝑘<1，000，000，000。

ligongzzz's solution

#include "iostream"

using namespace std;

int main() {
    long long n, m, k, x;
    cin >> n >> m >> k >> x;

    //计算10的i次方的余数
    long long base = 10 % n;
    long long result = 1;
    while (true) {
        long long temp = k % 10;
        for (int i = 0; i < temp; i++)
            result = result * base%n;
        k = k / 10;
        if (k == 0)
            break;
        //修改base的值
        long long baseTemp = base;
        for (int i = 0; i < 9; i++) {
            base = base * baseTemp % n;
        }
    }

    m = m * result%n;

    cout << (x + m) % n;

    return 0;
}

Neight99's solution

#include <cmath>
#include <iostream>

using namespace std;

int mods(int, int, int);

int main() {
    long long Answer;
    int n, m, k, x;

    cin >> n >> m >> k >> x;
    Answer = m * mods(10, k, n);
    Answer %= n;
    Answer += x;
    Answer %= n;
    cout << Answer << endl;

    return 0;
}

int mods(int x, int y, int n) {
    int Answer = 1;
    x %= n;
    while (y > 0) {
        if (y & 1) {
            Answer *= x;
            Answer %= n;
        }
        y /= 2;
        x = (x * x) % n;
    }

    return Answer;
}

yyong119's solution

#include<iostream>

using namespace std;

int PowerMod(long long a, long long b, long long c) {

    long long ans = 1;
    a %= c;
    for (; b; b >>= 1) {
        if (b % 2) ans = (ans * a) % c;
        a = a * a % c;
    }
    return ans % c;
}

int main() {

    ios::sync_with_stdio(false);

    long long n, m, k, x;
    cin >> n >> m >> k >> x;

    long long ans = PowerMod(10, k, n);
    ans = (ans * m % n + x) % n;
    cout << ans;

    return 0;
}