列表

详情

NC17487. Inverse Inverse Problem

描述

Here's a simple problem :

"Given integers A, B, X, N and a prime P, let f(x) = Ax + B and define fn(x) as f(f(...f(x)...)), where the function f is iterated n times. Calculate the value of fN(X) modulo P."

This is a classic problem, but have you ever tried the inverse problem?

"Given x, n, t, p, where 0 ≤ t < p ≤ n and p is a prime. Find nonnegative integers a, b where 1 ≤ a ≤ p - 1, 0 ≤ b ≤ p - 1 such that the answer to the testcase (A, B, X, N, P) = (a, b, x, n, p) is t, or determine if it's impossible."

This is still too easy, so now let's try to solve the inverse of the inverse problem.

For a testcase x, n, t, p to the inverse problem, define g(x, n, t, p) as -1 if there is no solution for a, b and the smallest possible value of a in a valid solution to this testcase otherwise. For example, g(1, 2, 31, 101) = 1 as a = 1, b = 15 is a valid solution.

Given an integer M, find a testcase x, n, t, p such that p ≤ M and the value of g(x, n, t, p) is maximal.

输入描述

The input contains a single integer, M (3 ≤ M ≤ 105).

输出描述

The output should contain 4 space-separated integers, x, n, t, p, denoting your testcase. The testcase must satisfy the constraints 1 ≤ x ≤ 109, 1 ≤ n ≤ 1018, 0 ≤ t < p ≤ M and p is prime.

Your testcase will be accepted if it satisfies all constraints and g(x, n, t, p) is maximum possible under the current constraints. If there are multiple solutions, you may output any of them.

示例1

输入: 

8

输出: 

2018 231 1 7

说明:

You can check that g(2018, 231, 1, 7) = 3. (For instance, a = 3, b = 4 is a solution and there are no solutions for a ≤ 2)

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 45ms, 内存消耗: 8852K, 提交时间: 2022-11-09 19:37:56 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+100;
int p[N],st[N],cnt;

void init()
{
    for(int i=2;i<N;i++)
    {
        if(!st[i])    p[cnt++]=i;
        for(int j=0;j<cnt && p[j]*i<N;j++)
        {
            st[p[j]*i]=1;
            if(i%p[j]==0)    break;
        }
    }
}
int ksm(int x,int y,int mod)
{
    int res=1;
    while(y)
    {
        if(y&1)    res=(res*x)%mod;
        x=(x*x)%mod;
        y=y>>1;
    }
    return res;
}

signed main()
{
    init();
    int m;
    cin>>m;
    int ma=0;
    int n,mod;
    
    for(int i=0;i<cnt && p[i]<=m;i++)
    {
        int a=1;
        int b=p[i]*(p[i]-1)/2;

        while(ksm(a,b,p[i]) != p[i]-1 )    a++;
        
        if(ma<a)
        {
            ma=a;
            n=b;
            mod=p[i];
        }
    }
    cout<<"1 "<<n<<" "<<mod-1<<" "<<mod<<endl;

}

C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 608K, 提交时间: 2018-08-14 10:47:55 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int table[][3] = {
  3, 2, 3,
  7, 3, 21,
  23, 5, 253,
  71, 7, 2485,
  311, 11, 48205,
  479, 13, 114481,
  1559, 17, 1214461,
  5711, 19, 16304905,
  10559, 23, 55740961,
  18191, 29, 165447145,
  31391, 31, 492681745,
};
 
int main(void) {
  int M;
  scanf("%d", &M);
  for (int i = 11 - 1; i >= 0; --i) {
    if (table[i][0] <= M) {
      printf("%d %d %d %d\n", 1, table[i][2], 0, table[i][0]);
      return 0;
    }
  }
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2018-08-09 15:15:09 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int table[][3] = {
  3, 2, 3,
  7, 3, 21,
  23, 5, 253,
  71, 7, 2485,
  311, 11, 48205,
  479, 13, 114481,
  1559, 17, 1214461,
  5711, 19, 16304905,
  10559, 23, 55740961,
  18191, 29, 165447145,
  31391, 31, 492681745,
};

int main(void) {
  int M;
  scanf("%d", &M);
  for (int i = 11 - 1; i >= 0; --i) {
    if (table[i][0] <= M) {
      printf("%d %d %d %d\n", 1, table[i][2], 0, table[i][0]);
      return 0;
    }
  }
}

上一题

© 2024 nowcoder.com