Hello my cp mates, I am stucked in a problem suppose I have to find sum of gcd(i,k) for all number i from 1......N. Here N is so big around N<=10^12. So we can't iterate through all the numbers from 1 to N. Have any alternative way???
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello my cp mates, I am stucked in a problem suppose I have to find sum of gcd(i,k) for all number i from 1......N. Here N is so big around N<=10^12. So we can't iterate through all the numbers from 1 to N. Have any alternative way???
Name |
---|
Auto comment: topic has been updated by _Hridoy (previous revision, new revision, compare).
Solving this problem requires some knowledge of inversion,
Then divide this equation into number theory blocks. Using Some Sublinear Sieves to Process Euler Functions For example, Du Jiaosieve.