蒟蒻の题解3 CF239A

gouTX · 2021-11-25 13:40:17 · 题解

前言：

本想着本大帅面对这种水题可以一遍过的，却没曾想，辣个男人竟然在这种题TLE了三遍！！！看来这道题还是不容小觑的。

题意：

已知三个数： y ，k ，n 。 现在又有一个数 x，要令 (x+y) mod k==0 ，且 x+y<=n ,求满足要求的所有 x 并输出。

首先，一个很容易想到的算法是：把一个数 i 从 1 循环到 n-y，若是找到一个满足 (i+y) mod k==0 的数 i，就把一个数 j 从 i 循环到 n-y，每次 j+=k。每循环一次就把 j 输出来，当 j>n-y 的时候，直接 return 0。如果 1 到 n-y 没有符合 (i+y) mod k==0 的数 i，输出 -1 就 OK。

于是就诞生了我的第一篇代码：

#include<iostream>
using namespace std;
int main()
{
    int y,k,n;
    cin>>y>>k>>n;
    for(int i=1;i<=n-y;i++)
    {
        if((i+y)%k==0) 
        {
            for(int j=i;j+y<=n;j+=k)
            {
                cout<<j<<' ';   
            }
            return 0;
        }
    }
    cout<<-1;
    return 0;
} 

很明显，TLE 了……

于是我就想：为了省时，能不能不用循环而用公式把最小的 x 算出来呢？

如果 (x+y) mod k==0，那么必有 x mod k + y mod k==k。

所以最小的 x 自然而然就是 k-y mod k 啦。

想到这点，AC 不就简简单单吗？

AC CODE:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int y,k,n;
    cin>>y>>k>>n;
    int x=k-y%k;
    if(x+y>n) //如果最小的 x 就大于 n-y 了，那么就没有满足要求的 x 了。
    {
        cout<<-1;
        return 0;
    }
    for(int i=x;i+y<=n;i+=k)
    {
        cout<<i<<' ';   
    }
    return 0;
}