Input: two positive integers n and K, and K positive integers with n are coprime.
$n≤10^6，k≤10^8$
You can quote the number of Coprime, and find that there is a cycle.
For example, 10
The 1379111317192123 272931333739 of its coprime
Horizontal groove section!!!!!
The circular section is equal to 4, the difference =10 (n) of each cycle.
So…
First deal with 1-N and N coprime.
Then find K’s loop section.
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define olinr return #define _ 0 #define love_nmr 0 #define DB double int n; int k; int num; int a[1005000]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } signed main() { n=read(); k=read(); for(int i=1;i<n;i++) if(__gcd(i,n)==1) a[++num]=i; put((k-1)/num*n+a[(k-1)%num+1]); //k-1/num：kThe number of loop sections before the loop is prevented from 0, so -1 re +1 olinr ~~(0^_^0)+love_nmr; }