甘肃党风廉政建设办网站百度竞价app

Description

话说， 小X是个数学大佬，他喜欢做数学题。有一天，小X想考一考小Y。他问了小Y一道数学题。题目如下：
对于一个正整数N，存在一个正整数T$（0<T<N）$，使得的值是正整数。
小X给出N，让小Y给出所有可能的T。如果小Y不回答这个神奇的大佬的简单数学题,他学神的形象就会支离破碎。所以小Y求你帮他回答小X的问题。

Input

一个整数N。

Output

第一个数M，表示对于正整数N，存在M个不同的正整数T，使得是整数。
后面是M个数，每一个数代表可能的正整数T（按从小到大的顺序排列）。

Sample Input

Sample Input1:
1

Sample Input2:
3

Sample Input3
180

Sample Output

Sample Output
0

Sample Output
1 2

Sample Output
5 120 144 160 168 176

Data Constraint

对于5%的数据，N=1.
对于20%的数据，N<=5.
对于40%的数据，N<=1000000
对于另外20%的数据，答案只有1个，且N为质数，保证对于前60%的数据，当N为质数的时候，答案都一定只有一个,对于这20%的数据，满足2

Solution

推导过程：
—>
—>
—>
—>

也就是说,我们要使的K是一个正整数,那么我们只需要让2K-1是N的(奇数)因数(当然1是不能算的)。我们就可以用的时间算出所有的因数,然后排一个序(因为的时间求因子是乱的),输出就可以了。(其中为因子)

注意细节:
·我们不能单纯输出而是输出因为int64会爆炸。
·排序要花费很多时间,时间复杂度其中num[-1]是因子个数。
·数组因子要开1000000。
·判因数的时候要判断的情况,但是不能被包含。这是因为有奇数判断的操作。

Code1

#include<cstdio> 
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 20000000
#define ll long long
using namespace std;
ll n,ans[N];
void qs(int l,int r){int i=l,j=r;ll m=ans[l];while(i<=j){while(ans[i]<m) i++;while(ans[j]>m) j--;if(i<=j){ll t=ans[i];ans[i]=ans[j];ans[j]=t;i++,j--;}}if(l<j) qs(l,j);if(i<r) qs(i,r);
}
int main(){freopen("math.in","r",stdin);freopen("math.out","w",stdout);scanf("%lld",&n);for(int i=1;i<=trunc(sqrt(n));i++){if((n%i)==0){if(i!=1&&i%2==1) ans[++ans[0]]=i;if(i*i!=n&&(n/i)%2==1) ans[++ans[0]]=n/i;}}qs(1,ans[0]);printf("%lld ",ans[0]);for(int i=1;i<=ans[0];i++) printf("%lld ",n/ans[i]*(ans[i]-1));return 0;
}

Code2

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
long long ys1[2500000],ys2[2500000];
int gs1=0,gs2=0;
int main()
{freopen("math.in","r",stdin);freopen("math.out","w",stdout);long long n,nn;scanf("%lld",&n);nn=n;while(n%2==0)n/=2;long long s=sqrt(n);for(long long i=1;i<=s;i+=2){if(n%i==0){if(i!=1)ys1[++gs1]=i;if(n/i!=1)if(n/i!=i)ys2[++gs2]=n/i;}}printf("%d ",gs1+gs2);long long k;for(int i=1;i<=gs1;i++){k=ys1[i]/2;printf("%lld ",nn/(2*k+1)*2*k);}for(int i=gs2;i>=1;i--){k=ys2[i]/2;printf("%lld ",nn/(2*k+1)*2*k);}printf("\n");fclose(stdin);fclose(stdout);return 0;
}

---

作者：zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/81556641