推出来了一个解法，但是感觉复杂度十分玄学，没想到秒过~
Code:
#include <bits/stdc++.h>
#define ll long long
#define N 50000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
namespace Math
{
ll pp,answer;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
ll ans=exgcd(b,a%b,x,y);
ll tmp=x;
x=y,y=tmp-a/b*y;
return ans;
}
void solve(ll A,ll B,ll C)
{
ll x,y,gcd,b,ans;
gcd = exgcd(A,B,x,y);
if(C%gcd!=0)
{
answer=-1;
return;
}
x*=C/gcd,B/=gcd;
if(B<0) B=-B;
ans=x%B;
if(ans<=0) ans+=B;
answer=ans,pp=B;
}
};
priority_queue<int,vector<int>,greater<int> >q;
map<int,int>mark;
vector<int>v;
int prime[N],vis[N],tot;
void init()
{
int i,j;
for(i=2;i<N;++i)
{
if(!vis[i]) prime[++tot]=i;
for(j=1;j<=tot&&prime[j]*i<N;++j)
{
vis[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
init();
// setIO("input");
int n,i,j,h,flag=0;
scanf("%d",&n),h=n;
for(i=1;i<=tot&&h>=prime[i];++i)
{
if(h%prime[i]==0)
{
int cc=1;
for(;h%prime[i]==0;h/=prime[i]) cc*=prime[i];
v.push_back(cc);
}
}
if(h!=1) v.push_back(h);
if(n%4==0) flag=1;
int len=v.size();
for(i=0;i<(1<<len);++i)
{
int tmp=1;
for(j=0;(1<<j)<=i;++j)
{
if(i&(1<<j))
tmp*=v[j];
}
int a=tmp,b=n/tmp,dd;
Math::solve(a,b,2);
if(Math::answer!=-1)
{
ll anss=Math::answer*a-1;
while(anss>=0&&anss<n)
{
if(!mark[anss]) mark[anss]=1,q.push(anss);
anss+=Math::pp*a;
}
}
swap(a,b);
Math::solve(a,b,2);
if(Math::answer!=-1)
{
ll anss=Math::answer*a-1;
while(anss>=0&&anss<n)
{
if(!mark[anss]) mark[anss]=1,q.push(anss);
anss+=Math::pp*a;
}
}
if(flag)
{
if(b%2==0) swap(a,b);
a/=2,b*=2;
Math::solve(a,b,2);
dd=Math::pp;
if(Math::answer!=-1)
{
ll anss=Math::answer*a-1;
while(anss>=0&&anss<n)
{
if(!mark[anss])
{
mark[anss]=1;
q.push(anss);
}
anss+=Math::pp*a;
}
}
swap(a,b);
Math::solve(a,b,2);
if(Math::answer!=-1)
{
ll anss=Math::answer*a-1;
while(anss>=0&&anss<n)
{
if(!mark[anss])
{
mark[anss]=1;
q.push(anss);
}
anss+=Math::pp*a;
}
}
}
}
while(!q.empty())
{
printf("%d\n",q.top()); q.pop();
}
return 0;
}