抽了窝bin 的数论中 几道比较基础的数学题， 来给学弟学妹入门这方面知识。
链接 密码 ｈｕｔａｃｍ
第一题： Light OJ 1336
题意： Ｆ（ｎ） 是 ｎ 的约数的和。 题目求 １ － ｎ 中有多少 Ｆ（ｎ） 为偶数。
思路： 题目给你了 相关知识， 一个数 ｎ 可以表示成 ｎ＝∏pi^ei 而 F（n） = (p1^(e1+1)-1)/(p1-1))*(p2^(e2+1)-1)/(p2-1))....
分析一下： 当 p 为 2 时， （p ^ （e + 1） - 1） / （p - 1） 总为奇数的
当 p ！= 2 时， 需探求 （p ^ （e + 1） - 1） / （p - 1） 奇偶性，
公式： a^n-b^n (其中n为正整数) =(a-b)[a^(n-1) + a^(n-2) *b +... + a*b^(n-2)+b^(n-1)]
得知当 n-1 为偶数的时候， [a^(n-1) + a^(n-2) *b +... + a*b^(n-2)+b^(n-1)] 有奇数项，
则可知 当 e 为偶数的时候， （p ^ （e + 1） - 1） / （p - 1）为奇数。
故此我们可以得出 对于 ｎ＝∏pi^ei ， 当 (pi != 2 && ei % 2 == 0) ==> F(n) 是奇数的---> F(2n) 也是奇数。
因为 ei 均为偶数 （ pi != 2 ），所以我们只要算出 1 - n 中有多少 平方数 和二倍平方数即可。
代码实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#define lson l , m, rt << 1
#define rson m+1, r, rt << 1|1
#define INF 0x7fffffff
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int main() {
int t;
cin >>t;
for(int kase = 1; kase <= t; kase++)
{
ULL n;
cin >>n;
ULL ans = 0;
for(ULL i = 1; i *i <= n; ++i)
{
ans ++;
if(2*i*i<= n) ans ++;
}
cout <<"Case "<<kase <<": "<< n-ans <<endl;
}
return 0;
}
第二题： LightOJ 1236 （其实这道题我抓错了， 哭瞎， 本来是 1245 的， 手贱， 不过也不是很难 ）
题意： 求有多少对数 ( i , j ) lcm (i , j ) == n && ( i <= n && j <= n)
思路： 有了第一题做基础， 这题就不难了。
首先介绍一下 lcm ， gcd 吧
N1 = p1 ^ e1 * p2 ^ e2 * p3 ^ e3 .......
N2 = p1 ^ s1 * p2 ^ s2 * p3 ^ s3 .......
gcd ( N1, N2 ) = p1 ^ min(e1, s1) * p2 ^ min(e2, s2) .....
lcm ( N1, N2 ) = p1 ^ max(e1, s1) * p2 ^ max(e2, s2) ....
如果 n % ( p ^ c ) == 0, 那么在 i， j中， 只有 ：
i % (p^c) == 0 && ( j % (p^0) == 0 || j % (p ^ 1) == 0 || .... || j % (p ^ c ) == 0 )， 共 c + 1 种
反之亦然， 故一个指数就可以产生 2 * c + 1 种
故 我们只需要分解给定的 N 就可以得出答案了。 （代码中 j >= i 的， 故 最后结果要 / 2）
实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#define lson l , m, rt << 1
#define rson m+1, r, rt << 1|1
#define INF 0x7fffffff
const long long maxn = 1e7 + 131;
const int MOD = 10000007;
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
LL Primes[maxn / 10], Count;
bool Jug[maxn];
void INT() {
Count = 0;
memset(Jug,0,sizeof(Jug));
for(LL i = 2; i <= maxn; ++i)
{
if(Jug[i] == 0)
{
Primes[Count++] = i;
for(LL j = i*i; j <= maxn; j += i) Jug[j] = 1;
}
}
}
int main() {
INT();
//for(int i = 0; i < 20; i++) cout << Primes[i] << endl;
int T;
cin >> T;
for(int kase = 1; kase <= T; ++kase)
{
ULL a;
ULL ans = 1;
cin >> a;
for(int i = 0; i < Count && Primes[i] * Primes[i] <= a; ++i)
{
if(a % Primes[i] ==0) {
LL tot = 0;
while(a % Primes[i] == 0) tot++, a /= Primes[i];
ans *= (tot*2+1);
}
}
if(a > 1) ans *= 3;
printf("Case %d: %llu\n",kase,(ans+ 1)/2 );
}
return 0;
}
第三题： Light OJ 1234
题意： 求 ∑ （1 / n）
思路： 有一堆数学公式， 但是也是可以打表过的。。。具体看代码吧
实现：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int num;
double s[1000010];
int main()
{
double temp = 1;
for(int i=2; i<=100000000; i++)
{
temp += 1.0/i;
if(i%100==0)
s[i/100] = temp;//分成100个每组打表.........O（1e8）
}
cin>>num;
int cn = 0;
int n;
double ans;
while(num--)
{
ans = 0;
cn++;
scanf("%d", &n);
ans = s[n/100];
for(int i=100*(n/100)+1; i<=n; i++)
{
ans += 1.0/i;
}
printf("Case %d: %.8f\n", cn, ans);
}
return 0;
}
第四题： LightOj 1214
题意： 判断 a % b == 0 的问题
思路： 看数据就知道是 大数问题， 也就是用字符串模拟 算术过程， 注意正负号就好了。
实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#define lson l , m, rt << 1
#define rson m+1, r, rt << 1|1
#define INF 0x7fffffff
const int maxn = 1e6 + 131;
const int MOD = 10000007;
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int main() {
string a;
LL b;
int T;
cin >> T ;
for(int kase = 1; kase <= T; kase++)
{
ULL ans = 0;
int cas = 0;
cin >> a >> b;
if(a[0] == ‘-‘) cas = 1;
if(b < 0) b = -b;
for(int i = cas; i < a.length(); ++i)
{
ans += a[i] - ‘0‘;
ans %= b;
ans = ans * 10 % b;
}
if(ans == 0) printf("Case %d: divisible\n",kase);
else printf("Case %d: not divisible\n",kase);
}
return 0;
}
原文：http://www.cnblogs.com/aoxuets/p/5244024.html