A. Anagrams
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
Consider the positional numeral system with a given base b. A positive integer x is called b-anagram of a positive integer y if they have the same length of representation in this system (without leading zeroes) and y can be obtained by rearranging the digits of x.
A positive integer k is called b-stable if for every integer m that is divisible by k all its b-anagrams are also divisible by k. Your task is to find all b-stable integers k for a given base b.
Input
The only line of the input contains an integer b — the base of the given positional numeral system (2 ≤ b ≤ 2·109).
Output
Print all b-stable integers k represented in the standard decimal numeral system. They must be printed in ascending order.
Sample test(s)
input
3
output
1 2
input
9
output
1 2 4 8
input
33
output
1 2 4 8 16 32
题意：给出一个进制b，有一数字k，有某种性质。
性质：这个数x整除于k，且在b进制下长度相等与x相等的所有数都能被k整除。
求对于这个b，所有满足这个性质的数。
分析：
1、找规律，b-1的所有因数既是答案
2、证明一下。
显然不能等于b。k=b，x=k就是一个反例。
若大于b，也是不科学的。因为x=b*k是一个反例
若小于b，那么对于长度相等这一条件，可以当成原来有一个可以整除的，任意交换两个数位，仍然整除。。。
即
bp*b^p+bp-1*b^(p-1)+.....+bi*b^i+......+bj*b^j+......b0*b^0 = 0 (mod k) ............ 1
bp*b^p+bp-1*b^(p-1)+.....+bj*b^i+......+bi*b^j+......b0*b^0 = 0 (mod k) ............... 2
若两式都是k的倍数，可知1式-2式也是k的倍数。
则(bi * b^i + bj * b^j) - (bj * b^i + bi * b^j)是k的倍数。
(bi * b^i + bj * b^j) - (bj * b^i + bi * b^j)
= (bi - bj) * (b^i - b^j)
= (bi - bj) * b^j * (b^(i - j) - 1)
这个(b^(i - j) - 1)肯定是b-1的正整倍数。
那么，当k|b-1的时候，显然成立。
否则就是每个位相等。。。。 如果每个位相等，
k = number * (b^p+b^(p-1)+......+b^2+b^1+1)
与k是一个不大于b的正整数矛盾。不科学。 所以k必定是b-1的因数。
/**
Create By yzx - stupidboy
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} int n; inline void Input()
{
cin >> n;
} inline void Solve()
{
n--;
vector<int> ans;
for(int i = ; i <= n; i++)
{
if(n / i < i) break;
if(n % i == )
{
ans.pub(i);
if(n / i != i) ans.pub(n / i);
}
}
sort(ans.begin(), ans.end());
int length = sz(ans);
for(int i = ; i < length; i++)
printf(i < length - ? "%d " : "%d\n", ans[i]);
} int main()
{
Input();
Solve();
return ;
}