给你一个数n，n不能被2,5整除，问你n的最小的每个数位全是1的倍数有多少位。
同余定理，另外这个题保证有解，所以相信自己，暴力出奇迹。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <cstdio> int main(){ int n = 0; while (scanf(" %d",&n) != EOF) { int cnt = 1; int base = 1; base %= n; while (base != 0) { base = ((base * 10)%n+1%n)%n; cnt++; } printf("%d\n",cnt); } return 0; } |
http://www.nocow.cn/index.php/Translate:Sgu/126，翻译版。
我是手写一些找规律，所以我也没办法细讲。
http://www.nocow.cn/index.php/Sgu/126详细题解，说是一个数论题，因为我是找规律所以代码肯定是写不严的，如果你需要严格证明请移步那边。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <cstdlib> #include <algorithm> using namespace std; int main(){ long long a = 0,b = 0,sum = 0; cin >> a >> b; sum = a+b; if(a == 0 || b == 0){ cout << 0 << endl; } if(sum%2){ cout << -1 << endl; return 0; } int res = 0; long long now = min(a,b); while(now != sum/2){ if(res > 10000){ cout << -1 << endl; return 0; } res++; now *= 2; now = min(now,sum-now); } cout << res+1 << endl; return 0; } |
给你n，让你输出n位数中平方后尾数是987654321的数的个数。
一个数，只考虑最后i位，那么这个数平方之后的最后i位和这个数的最后i位平方后的最后i位相同，所以我们只要考虑1～9位数中谁的平方最后9位是987654321就可以了，本地打个表，发现只有8个数符合要求，接下来，对于10位数，我们就有98=72种组合对于11位数就是908=720种组合，这样我们就发现了，超过10位数的话，就在73后面补上n-10个零就行了，这样大数时也搞定了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int main(){ int a = 0; scanf("%d",&a); if (a <= 8) { printf("0n"); }else if(a == 9){ printf("8n"); }else{ printf("72"); for (int i = 10; i < a; i++) { printf("0"); } printf("n"); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; #define MAXN 100005 int a[MAXN],b[MAXN],c[MAXN]; vector<int> d[MAXN]; void gen(){ for (int i = 1; i < MAXN; i++) { for (int j = 1; i * j < MAXN; j++) { d[i*j].push_back(i); } } } int vis[MAXN]; void solve(int n){ //-> memset(vis, -1, sizeof(vis)); for (int i = 1;i <= n; i++) { int now = a[i]; if (vis[now] != -1) { b[i] = vis[now]; } for (int j = 0;j < d[now].size(); j++) { vis[d[now][j]] = now; } if (b[i] == -1) { b[i] = now; } } //<- memset(vis, -1, sizeof(vis)); for (int i = n; i >= 1; i--) { int now = a[i]; if (vis[now] != -1) { c[i] = vis[now]; } for (int j = 0; j < d[now].size(); j++) { vis[d[now][j]] = now; } if (c[i] == -1) { c[i] = now; } } } int main(){ gen(); int n = 0; while(scanf(" %d",&n) != EOF && n){ memset(a, -1, sizeof(a)); memset(b, -1, sizeof(b)); memset(c, -1, sizeof(c)); for (int i = 1; i <= n; i++) { scanf(" %d",&a[i]); } solve(n); long long res = 0; for (int i = 1; i <= n; i++) { res += (long long)b[i] * (long long)c[i]; } printf("%lldn",res); } return 0; } |
智商鸿沟不可越系列。。。
思路是这样：首先对于1～100000每一个数生成一个约数表，方便以后查询，我们再建立一个int数组为vis，尺寸100000。接下来对于输入的数组，从左往右扫描，对于每一个数，如果vis[这个数]有值，说明当前数左端有倍数存在，最近的倍数就是这个vis值，没有的话，就是这个数本身，接下来读取当前数的每一个约数，对于每一个约数，当前数都是他们的倍数，所以更新vis[每一个约数]的值为当前数就可以了。
接下来方向反过来，从右到左扫描，算出c值，最统一出答案，小心别爆了int就行。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <stdio.h> #include <string.h> #include <ctype.h> #include <vector> #include <queue> using namespace std; #define MAXN 10005 vector<int> decomp(int n){ vector<int> res; for (int i = 2; i <= n; i++) { if (n % i == 0) { res.push_back(i); n /= i; i = 1; } } return res; } int main(){ int toQuery = 0; while (cin >> toQuery) { vector<int> dec = decomp(toQuery); sort(dec.begin(), dec.end()); dec.erase(unique(dec.begin(), dec.end()),dec.end()); for (int i = 0; i < dec.size(); i++) { toQuery *= dec[i]-1; toQuery /= dec[i]; } cout << toQuery << endl; } } |
这个题是欧拉函数：http://baike.baidu.com/view/107769.htm，正好就是这货的定义，说实话我都不知道欧拉函数是啥，打表又没意思了。。。
简单的说就是这个数挨个乘上(n-1)/n，n是不同的质因数。
贴一个求欧拉函数更好的姿势：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ll phi(ll n) { ll m=(ll)sqrt(n+0.5),ans=n; for(ll i=2;i<=m;i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0)n/=i; } } if(n>1)ans=ans/n*(n-1); return ans; } |
降幂公式 a^b %c= a^(b%phi(c)+phi(c)) %c （b>=phi(c)）
这个是意外收获，可以用到欧拉函数的地方。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main(){ unsigned int toQuery; while (cin >> toQuery) { int tmp = 0; if (toQuery % 3 == 2) tmp++; cout << 2*(toQuery/3)+tmp << endl; } return 0; } |
如果每一位加合等于3的话，这个数也可以被3整除。
然后打个表找下循环节发现是XOOXOOXOO这样的，直接简单判定一下实现就好了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define MAXN 1300000 bool prime[MAXN]; bool isPrime(int n){ for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } void genPrime(){ memset(prime, true, sizeof(prime)); for (int i = 2; i < MAXN; i++) { if (prime[i]) { if (isPrime(i)) { for (int k = 2; k * i < MAXN; k++) { prime[k*i] = false; } }else{ prime[i] = false; continue; } }else{ continue; } } } int main(){ genPrime(); int toQuery; while (cin >> toQuery) { if (!toQuery) { break; } int lbound = 0,rbound = 0; for (int i = toQuery; i >= 2; i--) { if (prime[i]) { lbound = i; break; } } for (int i = toQuery; i < MAXN; i++) { if (prime[i]) { rbound = i; break; } } cout << rbound - lbound << endl; } return 0; } |
埃氏筛法，没啥好说的嗯。